商务网站建设工程师是,门户网站建设需求,品牌设计主要做什么,新品发布会新闻稿New Year Garland
题意
用m种颜色的球装饰n层的圣诞树#xff0c;圣诞树的第i层由 l i l_{i} li个彩球串成#xff0c;且同一层相邻的球颜色不同#xff0c;相邻的层之间彩球颜色的集合不同#xff0c;问有多少种方案#xff0c;对p取模。
分析
首先先计算每一…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_{k1}^{min(m,\ l_{i-1})}{dp[i-1][k]} dp[i][j]j!∗(jm)∗g[li][j]∗k1∑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_{k1}^{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]∗k1∑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_{i1}^{min(m,\ l_{n})}{dp[n][i]} ansi1∑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;vectorint 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;
}
