题解：CF1784D Wooden Spoon

容易发现，一个人拿到木勺子的条件就是最终它往上的到根链上的 $n+1$ 个点的编号满足单调递减。这是一个很好 dp 的条件，因为它有很明显的可以递归的子结构。
我们发现这样的话，可以把填充除了到根链上的数的部分看作填充 $n$ 个胜者来自的子树。比如这个图，假设我们钦定的这个人位于 $12$ ，那么我们只需要填充子树 $13,7,2$ 。

这时候我们注意到一个关键性质：一个人能从一个子树中胜出当且仅当它是这个子树里面所有编号的最小值。

所以我们可以按照胜者编号从大到小来填充这些子树。为什么是从大到小呢？因为这样的话我们就不需要记录任何上一次填充用的数的相关信息，因为前一次填的数一定都在这一次能填的数的范围内，所以把这次能填的数去掉之前填了的数的总数，就是这次可以填的数集了。
这样并不是很好 dp，所以我们考虑一个“反向转移”的状态设计：记 $f_{i,j}$ 表示目前在第 $i$ 层（层数是从下往上分别为 $0\sim n$ ），该层胜出的数是 $j$ ，且 $j$ 在第 $i+1$ 曾经输掉了的方案数。

这个状态设计比较方便我们做类似于合并一条到根链上的所有子树的状态的事情。
转移我们考虑从上往下，考虑 $i+1$ 层的赢家 $k$ ，那么这里的贡献就是 $\sum\limits_{k=1}^{j-1}f_{i+1,k}$ 。然后考虑 $j$ 和第 $i$ 层的输家之间的贡献，也就是跟 $j$ 相邻的那个子树。

首先它们两个之间的顺序可以改变，所以是 $2$ 。

然后我们现在相当于确定了 $j$ 子树中有哪些数，也就是 $j$ 和输家一起的数的总数。这里我们发现，首先 $j$ 会赢 $0\sim i$ 中的每一层，所以我们如果考虑算 $j$ 子树中数的选择，就会很好算，因为它是较小的一边，另一个子树里能够选的数全在它能选的数集里面。所以这里的选法就是 $\binom{2^n-j-2^{i-1}}{2^{i-1}-1}$ ，其中 $2^n-j$ 是 $>j$ 的数的总数， $-2^{i-1}$ 是表示输家的子树会占掉 $2^{i-1}$ 个；然后 $2^{i-1}-1$ 是因为 $j$ 已经确定了。

最后我们考虑选出来的数的排列顺序。这里我们应该考虑的是 $j$ 隔壁的输家子树中 $2^{i-1}$ 个数的排列顺序，这是因为 $j$ 赢了 $0\sim i$ 的每一层，所以它的一部分子树还会往下传递，会在下面被计算；而输家子树之后就不会再被考虑了。并且在前面的决策之后，两个子树内的数集都已经确定。所以这里的贡献是 $(2^{i-1})!$ 。
省流： $f_{i,j}=\sum\limits_{k=1}^{j-1}f_{i+1,k}\times 2\times (2^{i-1})!\times \binom{2^n-j-2^{i-1}}{2^{i-1}-1}$ 。对 $f_{i+1}$ 前缀和优化一下就可以做到 $O\left(n2^n\right)$ 。
感觉就是一个类似于合并到根链状态的树形 dp 的题，主要难点在于在什么时候把“选数”和“排数”两个部分分开，并且发现这两个部分分别在什么顺序的时候好算。如果写到一个答案的表达式里面就类似于“交换求和顺序”一类的技巧吧。

CPP

#include <bits/stdc++.h>
using namespace std;
using tp = int;
constexpr tp INF = 1e9;
#define FULL(a) begin(a), end(a)
#define ALL(a, l, r) begin(a) + l, begin(a) + r + 1

template <typename T>
bool ckmax(T &x, T y) {
   if (y > x) return x = y, 1;
   return 0;
}
template <typename T>
bool ckmin(T &x, T y) {
   if (y < x) return x = y, 1;
   return 0;
}

constexpr tp mod = 998244353;
tp norm(tp x) { return x + (x < 0) * mod - (x >= mod) * mod; }
void add(tp &x, tp y) { x = norm(x + y); }
tp pow(tp x, tp y) {
   tp z = 1;
   for (; y; x = 1ll * x * x % mod, y >>= 1)
      if (y & 1) z = 1ll * z * x % mod;
   return z;
}

void QWQ() {
   //freopen(".in", "r", stdin), freopen(".out", "w", stdout);
   ios::sync_with_stdio(false), cin.tie(nullptr);
}

constexpr tp N = 21, M = (1 << 20) + 2;
tp n, m;
array<tp, M> f, g, fac, ifc;

tp bnm(tp n, tp m) {
   if (n < 0 || m < 0 || n < m) return 0;
   return 1ll * fac[n] * ifc[m] % mod * ifc[n - m] % mod;
}

tp HARUTO() {
   cin >> n, m = 1 << n;
   fac[0] = 1;
   for (tp i = 1; i <= m; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
   ifc[m] = pow(fac[m], mod - 2);
   for (tp i = m - 1; ~i; --i) ifc[i] = 1ll * ifc[i + 1] * (i + 1) % mod;

   f[0] = 1;
   for (tp i = n; ~i; --i) {
      tp c = 1 << i - 1;
      g[0] = f[0], f[0] = 0;
      for (tp j = 1; j <= m; ++j) g[j] = norm(f[j] + g[j - 1]), f[j] = 0;
      if (i < 1) break;
      for (tp j = 1; j <= m; ++j) f[j] = 2ll * g[j - 1] * fac[c] % mod * bnm(m - j - c, c - 1) % mod;
   }
   for (tp i = 1; i <= m; ++i) cout << g[i - 1] << "\n";
   return 0;
}

int main() {
   QWQ();
   tp t = 1;
   while (t--) HARUTO();
   return 0;
}

题解：CF1784D Wooden Spoon

文章操作

相关推荐

评论

题解：CF1784D Wooden Spoon