南昌网站建设一般多少钱一年公司企业网站制作
New Year Garland
题意
用m种颜色的球装饰n层的圣诞树,圣诞树的第i层由 l i l_{i} li个彩球串成,且同一层相邻的球颜色不同,相邻的层之间彩球颜色的集合不同,问有多少种方案,对p取模。
分析
首先先计算每一层各种小球选取情况下的方案数,因为限制每层小球只有 l i l_{i} li个,且 l i ≤ 5000 l_{i} \leq 5000 li≤5000,所以可以预处理出 g [ l i ] [ j ] g[l_{i}][j] g[li][j]表示 l i l_{i} li个球中有 j j j种颜色时放置的方案数,递推方程就是
g [ i ] [ j ] = g [ i − 1 ] [ j − 1 ] + g [ i − 1 ] [ j ] ∗ ( j − 1 ) g[i][j]=g[i-1][j-1]+g[i-1][j]*(j-1) g[i][j]=g[i−1][j−1]+g[i−1][j]∗(j−1)
边界是 g [ 0 ] [ 0 ] = 1 g[0][0]=1 g[0][0]=1,递推方程的意思是要么在第 i − 1 i-1 i−1个球后面放一个未出现的颜色的小球,要么放一个已经出现过的颜色的小球,因为相邻颜色不同,所以有 ( j − 1 ) (j-1) (j−1)种方式,第i层放j种颜色小球的放置方案数就成了
j ! ∗ ( m j ) ∗ g [ l i ] [ j ] j!*\binom{m}{j}*g[l_{i}][j] j!∗(jm)∗g[li][j]
然后再考虑层与层之间的限制,假如没有这个限制的话,dp就可以写成
d p [ i ] [ j ] = j ! ∗ ( m j ) ∗ g [ l i ] [ j ] ∗ ∑ k = 1 m i n ( m , l i − 1 ) d p [ i − 1 ] [ k ] dp[i][j]=j!*\binom{m}{j}*g[l_{i}][j]*\sum_{k=1}^{min(m,\ l_{i-1})}{dp[i-1][k]} dp[i][j]=j!∗(jm)∗g[li][j]∗k=1∑min(m, li−1)dp[i−1][k]
加上限制后,只需要减去相同颜色集合的对应方案数即可,那就成了
d p [ i ] [ j ] = j ! ( ( m j ) ∗ g [ l i ] [ j ] ∗ ∑ k = 1 m i n ( m , l i − 1 ) d p [ i − 1 ] [ k ] − g [ l i ] [ j ] ∗ d p [ i − 1 ] [ j ] ) dp[i][j]=j!(\binom{m}{j}*g[l_{i}][j]*\sum_{k=1}^{min(m,\ l_{i-1})}{dp[i-1][k]}-g[l_{i}][j]*dp[i-1][j]) dp[i][j]=j!((jm)∗g[li][j]∗k=1∑min(m, li−1)dp[i−1][k]−g[li][j]∗dp[i−1][j])
最终的答案就是
a n s = ∑ i = 1 m i n ( m , l n ) d p [ n ] [ i ] ans = \sum_{i=1}^{min(m,\ l_{n})}{dp[n][i]} ans=i=1∑min(m, ln)dp[n][i]
现在思考一下能够预处理的是 g [ l i ] [ j ] g[l_{i}][j] g[li][j]以及 j ! j! j!。 ( m j ) \binom{m}{j} (jm)好似能预处理出来,又好似因为p不一定是素数,不一定能求逆,尝试把 j ! j! j!带入方程观察,发现 ( m j ) \binom{m}{j} (jm)就变成了 A m j A_{m}^{j} Amj,可以开心的预处理了。前面都解决了,但里面还有一个 d p [ i − 1 ] [ k ] dp[i-1][k] dp[i−1][k]的求和每次都要跑满循环,再次观察能否 O ( 1 ) O(1) O(1)求出。当然一定是可以边计算边求出上一轮dp的和,所以这个值也可以 O ( 1 ) O(1) O(1)求出了。边界就是第一轮的dp的和为1。但这就结束了嘛?显然没有:(。因为 n ≤ 1000000 n \leq 1000000 n≤1000000导致dp数组空间巨大,此时,不难发现,该轮的dp只与上一轮的dp值有关,即好似可以滚动数组优化之类的操作,用两个数组即可完成dp过程。
AC代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int g[5010][5010], fac[5010], fac1[1000010], dp[5010], tmp[5010];
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m, p;cin >> n >> m >> p;vector<int> l(n + 1);for (int i = 1; i <= n; i++) {cin >> l[i];}g[0][0] = 1;for (int i = 1; i <= 5000; i++) {for (int j = 1; j <= i; j++) {g[i][j] = (g[i - 1][j - 1] + 1LL * (j - 1) * g[i - 1][j] % p) % p;}}fac[0] = 1;for (int i = 1; i <= 5000; i++) {fac[i] = 1LL * fac[i - 1] * i % p;}fac1[0] = 1;for (int i = 1; i <= m; i++) {fac1[i] = 1LL * fac1[i - 1] * (m - i + 1) % p;}LL sum = 1;for (int i = 1; i <= n; i++) {LL res = 0;for (int j = 1; j <= l[i]; j++) {tmp[j] = (1LL * fac1[j] * g[l[i]][j] % p * sum % p - 1LL * fac[j] * g[l[i]][j] % p * dp[j] % p + p) % p;res = (tmp[j] + res) % p;}sum = res;for (int j = 1; j <= l[i - 1]; j++) {dp[j] = 0;}for (int j = 1; j <= l[i]; j++) {dp[j] = tmp[j];}}cout << sum << '\n';return 0;
}