NOIP 模拟赛 长寿花 题解

NOIP 模拟赛 长寿花 题解

要放 n 层物品，第 i 层有 ai 个位置放物品，物品有 m 中颜色，有约束条件：

求方案数 (modp)

n,m≤106,ai≤5000,∑ni=1ai≤107,p≤109

sol

由于总颜色数不变，可以先不管选了哪些颜色，最后乘上一个组合即可。

设 gi,j 为对于某一行，前 i 个位置用了 j 个颜色方案数。

gi,j=gi−1,j−1×j+gi−1,j×(j−1)

由于后面需要求组合数，稍加修改这个递推式可以简化实现：

gi,j=gi−1,j−1+gi−1,j×(j−1)

那么原来的 gi,j 等于现在的 gi,j×j!

设 fi,j 为前 i 层，第 i 行放了 j 种颜色的方案数。

fi,j=gai,j×j!×(Cjm×ai−1∑k=1fi−1,k−fi−1,j)

由于有组合数， P 也不一定是质数，分解质因数麻烦，这就体现修改后的用处了。

j!×(mj)=m!(m−j)! ，是可以预处理的。

最后， f 滚掉一维，那个 ∑ 用前缀和。最终复杂度 O(∑ai)

code

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long uLL;

typedef long double LD;

typedef double db;

const int N = 1e6 + 5;

int n, m, a[N], mx, op, vis[N], P;

int f[2][5005], g[5005][5005], fac[N], o[N];

int main() {

scanf("%d%d%d", &n, &m, &P);

fac[0] = 1, o[0] = 1;

for (int i = 1; i <= m; i++) fac[i] = 1ll * fac[i - 1] * i % P, o[i] = 1ll * o[i - 1] * (m - i + 1) % P;

for (int i = 1; i <= n; i++) {

scanf("%d", &a[i]);

mx = max(mx, a[i]);

}

g[0][0] = 1;

for (int i = 1; i <= mx; i++)

for (int j = 1; j <= mx && j <= m; j++)

g[i][j] = (1ll * g[i - 1][j - 1] % P + 1ll * g[i - 1][j] * (j - 1) % P) % P;

f[0][0] = 1;

for (int i = 1, j; i <= n; i++) {

op ^= 1;

memset(f[op], 0, sizeof(f[op]));

for (j = 1; j <= a[i] && j <= m; j++) {

f[op][j] = 1ll * g[a[i]][j] * f[op ^ 1][0] % P * o[j] % P;

if (a[i - 1] >= j) f[op][j] = 1ll * (f[op][j] - 1ll * f[op ^ 1][j] * g[a[i]][j] % P * fac[j] % P) % P;

f[op][0] = 1ll * (f[op][0] + f[op][j]) % P;

}

}

printf("%d", 1ll * (f[op][0] + P) % P);

}