题解：CF1784D Wooden Spoon

· · 题解

考虑使用动态规划解决问题。

首先我们称树从上到下共 n + 1 层，第 i 层有 2^{i - 1} 个点，这一层每个点的子树的叶子节点数量为 2^{n - i + 1}。

接下来，令 dp_{i, j} 表示考虑到第 i 层（第 n - i + 1 轮），赢家 j 后面满足木勺奖那些限制（就是后面一直输）的方案数。显然 dp_{1, j} 的意义是最后一轮谁是赢家，有 dp_{1, 1} = 1，其它初始值为 0。

然后考虑转移。假设现在需要转移的是 dp_{i, j} \leftarrow dp_{i - 1, k}，则需要让 j 和 k 打一场并且 j 输掉（j > k）。令 m = 2^{n - i + 1} 表示第 i 层单个节点的子树的叶子节点数量（实际意义是子树的“参赛席位”数量）。由于 j > k 且 j 是以他为根的子树的赢家（子树中最小值），因此 j 及其子树这 m 个点的值一定均 \geq j > k。另外，k 作为第 i - 1 层的节点，他在第 i 层时一定是其所在叶子节点数为 m 的子树中最小的那个，即其余 m - 1 个点都 > k。于是，k 在第 i 层时子树内最底层其余 m - 1 个点的值一定选自 (k, 2^n] 中且不是 j 及其子树的 m 个，方案数为 (2^n - k) - m 选 m - 1，即 \binom{2^n - k - m}{m - 1}。

刚才的式子帮我们确定了人员。不过我们不关心 j 和 k 二者在第 i 层到底谁左谁右，因此转移系数需要 \times 2；同理，我们关心 k 子树内 m 个叶子的排列顺序，因此要乘 m!。

综上，我们可以得出总转移方程：

dp_{i, j} = 2 \times (2^{n - i + 1})! \times \sum\limits_{k < j} \binom{2^n - k - 2^{n - i + 1}}{2^{n - i + 1} - 1} \times dp_{i - 1, k}

用前缀和优化一下，可以做到总时间复杂度 \mathcal{O}(2^n n)，最终答案 dp_{n + 1, *}。

:::info[参考代码]{open}

提交记录：https://codeforces.com/contest/1784/submission/374364419。

#include<bits/stdc++.h>
// #define int long long
#define fo(i, l, r) for(decltype((l) + (r)) i = (l); i <= (r); ++i)
#define fd(i, l, r) for(decltype((l) + (r)) i = (l); i >= (r); --i)
#define fu(i, l, r) for(decltype((l) + (r)) i = (l); i <  (r); ++i)
#define y1 zhang_kevin
#define pii pair<int, int>
#define fi first
#define se second
#define vec vector
#define pb push_back
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define ll long long
#define ull unsigned long long
#define flush() (fwrite(obuf, 1, p3 - obuf, stdout), p3 = obuf)
using namespace std;
bool ST;
char ibuf[1 << 20], *p1 = ibuf, *p2 = ibuf, obuf[1 << 20], *p3 = obuf;
inline char gc(){
    if(p1 == p2){
        p1 = ibuf, p2 = ibuf + fread(ibuf, 1, 1 << 20, stdin);
        if(p1 == p2) return EOF;
        return *p1++;
    }
    return *p1++;
}
inline char pc(char ch){
    if(p3 == obuf + (1 << 20)) flush();
    *p3 = ch;
    return *p3++;
}
template<typename type>
inline int rd(type &x){
    x = 0; bool f = 0; char ch = gc();
    while(!isdigit(ch)) f |= ch == '-', ch = gc();
    while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
    return f ? x = -x : 0;
}
template<typename type, typename ...T>
inline void rd(type &x, T &...y){rd(x), rd(y...);}
inline void gs(string &s){
    s.clear(); char c = gc();
    while(c == ' ' || c == '\n' || c == '\t' || c == '\r') c = gc();
    while(c != ' ' && c != '\n' && c != '\t' && c != '\r' && c != EOF) s += c, c = gc();
    return;
}
class Flush{public: ~Flush(){flush();}}___;
template<typename type>
inline void wr(type x){
    if(x < 0) pc('-'), x = -x;
    if(x > 9) wr(x / 10);
    pc(x % 10 + '0');
    return;
}
inline void wrs(const string& s){for(auto ch : s) pc(ch);}
namespace Solution{
    const int N = 25, M = (1 << 20) + 5, mo = 998244353;
    int n, fac[M], inv[M], p2[N], dp[N][M], s[N][M];
    inline int fp(int a, int b){
        int res = 1;
        while(b){
            if(b & 1) res = (ll)res * a % mo;
            a = (ll)a * a % mo;
            b >>= 1;
        }
        return res;
    }
    inline int mod(ll x){return (x % mo + mo) % mo;}
    inline int C(int n, int m){
        if(n < m) return 0;
        return (ll)fac[n] * inv[m] % mo * inv[n - m] % mo;
    }
    inline void Solve(){
        rd(n); const int m = (1 << n);
        fac[0] = 1; fo(i, 1, m) fac[i] = (ll)fac[i - 1] * i % mo;
        inv[m] = fp(fac[m], mo - 2); fd(i, m, 1) inv[i - 1] = (ll)inv[i] * i % mo;
        p2[0] = 1; fo(i, 1, n) p2[i] = (ll)p2[i - 1] * 2;
        dp[1][1] = 1; fo(i, 1, m) s[1][i] = 1;
        fo(i, 2, n + 1){
            fo(j, 1, m){
                dp[i][j] = (ll)2 * fac[p2[n - i + 1]] % mo * s[i - 1][j - 1] % mo;
                int t = C(p2[n] - j - p2[n - i], p2[n - i] - 1);
                s[i][j] = (s[i][j - 1] + (ll)t * dp[i][j] % mo) % mo;
            }
        }
        fo(i, 1, m) wr(dp[n + 1][i]), pc('\n');
        return;
    }
}
bool ED;
signed main(){
    clock_t START = clock();
    // freopen("input.in", "r", stdin), freopen("output.out", "w", stdout);
    Solution::Solve();
    cerr << (double)(clock() - START) / CLOCKS_PER_SEC << " s" << '\n';
    cerr << 1.0 * abs(&ED - &ST) / 1024 / 1024 << " MB" << '\n';
    return 0;
}

:::