【题解】[USACO19DEC]Tree Depth P

· · 题解

更好的体验尽在我的博客。

不用生成函数，目前比 rank2 快四倍。

首先这是一道不简单的数数思维题。

我们要统计对于所有排列的深度之和，直接做非常不方便。而数数题一般将条件化简，或找到等价的容易处理的条件。

这里求深度，等价于枚举一个点的祖先，它的祖先个数 +1 就是它的深度。这样问题转化为求数对 (u,v) 的贡献，即有多少排列使得 v 是 u 的祖先。

如果 v 是 u 的祖先，等价于 a_v < a_u，且 u,v 之间没有小于 a_v 的数。

如果不考虑其它限制条件，先求有多少个排列恰好有 K 个逆序对。这是一个经典题目，直接定义状态 f_{i,j} 表示长度为 i 的逆序对数为 j 的排列个数。枚举最后一位的 i 种选择，分别是逆序对增加 x\in[0,i - 1] 个，典型的背包模型，可以前缀和优化至 \mathcal{O}(N^3)。

现在有 (u,v) 的限制条件，我们可以先固定 u,v 之间的数，再固定 u,v，最后固定外面的数。不难发现除了位置 v，其余的数可以随便填，和上面的转移一模一样。对于位置 v，如果在 u 后面，一定会产生 v-u 个逆序对，否则一定不产生逆序对。

所以我们先跑 DP 求出 f。然后枚举 v-u，然后在背包中撤销 (v-u)，撤销后的 f_{n - 1,K-\max(0,v-u)} 就是我们要求的贡献。

时间复杂度 \mathcal{O}(N^3)，代码没有一次乘法和取模，跑的飞快。

#define M 46600
#define N 305
int n, k, f[2][M], s[M], g[M], sz, ans[N];
#define ck(x) (x >= P ? x - P : x)
void undo(int x){
    memset(g, 0, sizeof(g));
    int cur = P - 1; g[0] = 1;
    rp(i, sz - x){
        if(i > x)ad(cur, g[i - x - 1]);
        su(cur, g[i] = ck(f[n & 1][i] + cur));
    }
}
int main() {
    read(n, k, P);
    f[0][0] = 1;
    rp(i, n){
        s[0] = f[i & 1][0] = 1, sz += i - 1;
        rp(j, sz){
            f[i & 1][j] = s[j] = ck(s[j - 1] + f[1 & (i - 1)][j]);
            if(j >= i)su(f[i & 1][j], s[j - i]);
        }
    }
    rp(i, n)ans[i] = f[n & 1][k];
    rp(t, n - 1){
        undo(t);
        rp(i, n - t){
            if(t <= k)ad(ans[i], g[k - t]);
            ad(ans[i + t], g[k]);
        }
    }
    rp(i, n)printf("%d ", ans[i]); el;
    return 0;
}