题目描述：（暂不提供）
这道题考场没来得及看。
很显然这是一道 D P DP DP题。 首先我们设： g i , j g_{i,j} gi,j为 i i i个位置， j j j种装饰，相邻两两不同装饰种类的方案数。 只考虑 1 − j 1-j 1−j种装饰。 g i , j = g i − 1 , j ∗ ( j − 1 ) + g i − 1 , j − 1 ∗ j g_{i,j}=g_{i-1,j}*(j-1) +g_{i-1,j-1}*j gi,j=gi−1,j∗(j−1)+gi−1,j−1∗j。 对于第一项，前面已经有 j j j种装饰，那就可以任意填 j − 1 j-1 j−1种装饰。 对于第二项，前面有 j − 1 j-1 j−1种装饰，你并不知道前面 j − 1 j-1 j−1种装饰包含 1 − j 1-j 1−j中的哪一种，所以乘上 j j j。
然后设 f i , j f_{i,j} fi,j表示第 i i i行选 j j j种装饰的方案 于是枚举 k k k来被转移。 当 k k k不等于 j j j的时候： f i , j ∗ [ C m k ∗ g a i , k ] − > f i + 1 , k f_{i,j}*[C_{m}^k*g_{a_{i},k}] -> f_{i+1,k} fi,j∗[Cmk∗gai,k]−>fi+1,k 当 k k k等于 j j j的时候： f i , j ∗ [ ( C m k − 1 ) ∗ g a i , k ] − > f i + 1 , k f_{i,j}*[(C_{m}^k-1)*g_{a_{i},k}]->f_{i+1,k} fi,j∗[(Cmk−1)∗gai,k]−>fi+1,k
然后整合一下： f i , j = [ C m k ∗ g a i , j ∗ Σ k f i − 1 , k ] − f i − 1 , j ∗ g a i , j f_{i,j}=[C_{m}^k*g_{a_{i},j}*\Sigma_{k}f_{i-1,k}]-f_{i-1,j}*g_{a_{i},j} fi,j=[Cmk∗gai,j∗Σkfi−1,k]−fi−1,j∗gai,j 然后注意到 Σ k f i − 1 , k \Sigma_{k}f_{i-1,k} Σkfi−1,k是可以上一次算好的。所以 f i , j f_{i,j} fi,j的转移就是 O ( 1 ) O(1) O(1)的。
然后注意下组合数要用分解质因数来算。
经过 Z J J ZJJ ZJJ的辅导，总算是调出来了。 时限给了5 s s s，然后我跑了一秒半。 吸了氧以后就跑进1 s s s了。
%:pragma GCC optimize(2) %:pragma GCC optimize("Ofast") %:pragma GCC optimize("inline") #include <cstdio> #include <cstring> using namespace std; const int N = 5010; const int M = 1000010; inline void read(int &x) { char ch = getchar(); x = 0; for(;ch < '0' || ch > '9';) ch = getchar(); for(;ch >= '0' && ch <= '9';) x = x * 10 + (ch ^ '0'), ch = getchar(); } int cnt = 0,p[M],vis[M],c[M],t[M]; int tot = 0,used[M],f[2][N],g[N][N]; int n,m,mod,a[M],pre,ans; inline void Get_p() { for(int i = 2;i < M; ++ i) { if(!vis[i]) p[++cnt] = i; for(int j = 1;j <= cnt && i * p[j] < M; ++ j) { vis[i * p[j]] = 1; if(i % p[j] == 0) break; } } } inline int f_pow(int a,int x) { int ret = 1; for(;x;x >>= 1) (x & 1) && (ret = 1ll * ret * a % mod), a = 1ll * a * a % mod; return ret; } inline void inc(int x) { for(int i = 1;i <= cnt && p[i] * p[i] <= x; ++ i) if(x % p[i] == 0) { if(!vis[p[i]]) used[++tot] = p[i],vis[p[i]] = 1; for(;!(x % p[i]);x /= p[i]) ++t[p[i]]; } if(x > 1) { if(!vis[x]) used[++tot] = x,vis[x] = 1; ++t[x]; } } inline void dec(int x) { for(int i = 1;i <= cnt && p[i] * p[i] <= x; ++ i) if(x % p[i] == 0) for(;!(x % p[i]);x /= p[i]) --t[p[i]]; if(x > 1) --t[x]; } inline int calc(int x,int y) { int ret = 1; inc(x), dec(y); for(int i = 1;i <= tot; ++ i) ret = ret * 1ll * f_pow(used[i],t[used[i]]) % mod; return ret; } int main() { freopen("kalanchoe.in","r",stdin); freopen("kalanchoe.out","w",stdout); read(n), read(m), read(mod); for(int i = 1;i <= n; ++ i) read(a[i]); Get_p(); g[1][1] = 1; pre = 1; memset(c,0,sizeof c), memset(vis,0,sizeof vis); for(int i = 2;i < N; ++ i) for(int j = 1;j <= i; ++ j) g[i][j] = (1ll * g[i - 1][j] * (j - 1) + 1ll * g[i - 1][j - 1] * j) % mod; for(int i = 1;i <= m && i <= 5000; ++ i) c[i] = calc(m - i + 1,i); for(int i = 1;i <= n; ++ i) { for(int j = 1;j <= a[i] && j <= m; ++ j) f[i & 1][j] = (1ll * c[j] * g[a[i]][j] % mod * pre - 1ll * f[i & 1 ^ 1][j] * g[a[i]][j]) % mod; pre = 0; for(int j = 1;j <= a[i]; ++ j) pre = (pre + f[i & 1][j]) % mod; if(i > 1) for(int j = a[i] + 1;j <= a[i - 2]; ++ j) f[i & 1][j] = 0; //这里清零是因为可能会因为a的值不同而造成的虚假贡献 } for(int i = 1;i <= m && i <= a[n]; ++ i) ans = (ans + f[n & 1][i]) % mod; printf("%d",(ans + mod) % mod); fclose(stdin); fclose(stdout); return 0; }当然空间也要注意， f f f数组是可以滚动的。
