题解：CF2001E1 Deterministic Heap (Easy Version)

· · 题解

写篇题解！
首先根据套路，不难设计出状态 f_{i,j} 表示一颗层数为 i 的二叉树，根节点的值为 j 时的合法方案数。（显然对于每一颗层数为 i 的二叉树，情形类似）。
之后根据题意，可以转移的充要条件即是根节点的两个儿子权值不等（这样一定是往权值大的儿子的子树转移，与另一颗无关）。所以我们由此设计出另一状态，g_{i,j} 表示一颗 i 层的二叉树根节点值为 j 的任意方案数（即无需关注是否合法）。
可以得到：

\begin{equation*} \large{f_{i,j} = 2 \times \sum_{x=0}^j \sum_{y=\lfloor \frac{x}{2} \rfloor +1}^{x}} f_{i+1,y} \times g_{i+1,x-y} \end{equation*}

这个式子的本质就是：枚举根节点两个儿子的和 x（因为根节点的值可能有部分是直接选中根节点而来的）。同时由 x 枚举较大的儿子值 y，表明下次要进入 y 侧的子树，所以此侧需要是合法的方案数 f，另一侧就是任意的 g 了。（因为左右子树情况等价所以还需乘 2）。

同理，我们也可以得到 g 的转移式：

\begin{equation*} \large{g_{i,j} = \sum_{x=0}^j \sum_{y=0}^{x}} g_{i+1,y} \times g_{i+1,x-y} \end{equation*}

区别就是 g 的转移不需要关注根节点儿子的值的相对大小。
由此得到了一种 \mathcal{O(nm^3)} 的做法，显然无法通过。所以我们需要考虑降复杂度（即少掉一个 \sum）。
观察得知，枚举 x 过于累赘，我们不如直接枚举较大的儿子值 y。那么另一颗子树可以取的值即为 0 \to \text{min}(y-1,j-y)（表示另一颗子树的值必然小于 y，且两棵子树的和应小于根节点的值 j）。这里就可以通过前缀和优化了。

\begin{equation*} \large{f_{i,j} = 2 \times \sum_{x=0}^j \ \ f_{i+1,x} \sum_{y=0}^{\text{min}(x-1,j-x)} g_{i+1,y}} \end{equation*}

这里的 x 即是上述的 y，y 既是 x 对映的范围。
同样地，g 也可以做类似优化

\begin{equation*} \large{g_{i,j} = \sum_{x=0}^j \ \ g_{i+1,x} \sum_{y=0}^{j-x} g_{i+1,y}} \end{equation*}

最后的 \sum 均可通过前缀和 \mathcal{O}(1) 求出，所以复杂度降为 \mathcal{O}(nm^2)，可以通过。
给出核心代码：

inline void Solve() {
    scanf("%d %d %d", &n, &K, &P);
    Sg[0] = 0ll;      
    for (int i = 0; i <= K; i++) {
        f[1][i] = g[1][i] = 1ll;
        Sg[i + 1] = (Sg[i] + g[1][i]) % P;
    }   
    for (int i = 2; i <= n; i++) {         
        auto Sumg = [&](int l, int r) {                  
            return l > r ? 0ll : (Sg[r + 1] - Sg[l]) % P;    
        };  
        for (int j = 0; j <= K; j++) {  
            f[i][j] = g[i][j] = 0ll;
            for (int x = 0; x <= j; x++) {
                f[i][j] = (f[i][j] + 2ll * f[i - 1][x] * Sumg(0, std::min(x - 1, j - x)) % P) % P;
                g[i][j] = (g[i][j] + 1ll * g[i - 1][x] * Sumg(0, j - x) % P) % P;
            }   
        } 
        Sg[0] = 0ll; for (int j = 0; j <= K; j++) Sg[j + 1] = (Sg[j] + g[i][j]) % P;      
    } 
    printf("%lld\n", f[n][K]);  
    return;  
}

更多思考，其实求解 g_{i,j} 的值可以转化为经典的组合数学问题。即有 2^{i}-1 个数，要选 j 个（选的数可以重复），求方案数。
考虑通俗化，有 n 个数，要选 m 个，可以重复选，求方案数。设 x_i 表示第 i 个数被选了几次，那答案等价于

x_1+x_2+x_3+...+x_n=m

有多少组非负整数解。我们设 y_i=x_i+1，所以又等价于

y_1+y_2+y_3+...+y_n=m+n

有多少组正整数解（因为一个 y_i 对映一个 x_i）。
根据经典的隔板法，考虑有 m+n 个 1，其中有 m+n-1 个空隙，而你只要在这 m+n-1 中档 n-1 个板，就可以将这若干个 1 分成 n 份，其中每一份的和就是一组解中 y_i 的值。因此答案即为 \binom{m+n-1}{n-1} = \binom{m+n-1}{m}。

因此 \large{g_{i,j}= \binom{2^{i}+x-2}{x}}。