【fjwc2015】圣诞树

2015年2月4日1,2660

【题目描述】

用m种颜色的彩球装点n层的圣诞树。圣诞树的第i层恰由l[i]个彩球串成一行,且同一层内的相邻彩球颜色不同,同时相邻两层所使用彩球的颜色集合不同。求有多少种装点方案,答案对p取模。

只要任一位置上的彩球颜色不同,就算作不同的方案。

【输入格式】

第一行三个整数n,m,p,表示圣诞树的层数、彩球的颜色数和取模的数。

接下来一行包含n个整数,表示l[i]。

【输出格式】

一个整数表示答案。

【样例输入】

3 2 1000

3 1 2

【样例输出】

8

【数据范围】

对于30%的数据,m <= 2, Σl[i] <= 10

对于60%的数据,n <= 20, l[i] <= 100

对于100%的数据,1 <= n,m <= 10^6, 2 <= p <= 10^9, 1 <= l[i] <= 5000, Σl[i] <= 10^7

题解

30%直接2^∑l[i]爆搜判断即可

100%

搬运coolinging神犇学长的题解

题目来源:CodeForces 140 E

考察要点:动态规划、组合数学

先考虑小问题:恰用j种颜色布置一行i个球的方案数dp[i][j]。

用类似于最小表示法的思想,我们要求x号颜色的首次出现位置必须比x+1号颜色的早,这样一来将所求得的方案数乘以颜色的全排列数j!就是原来的方案数。

若前i-1个球使用了j-1种颜色,则第i个球必然使用了第j种颜色;若前i-1个球已使用了j种颜色,则第i个球使用的颜色必须与第i-1个球不同,所以有(j-1)种方案。故可由简单的dp递推而得:

F[i][j] = F[i-1][j-1] + F[i-1][j] * (j-1)

现在考虑相邻两层之间的限制,用d[i][j]表示前i层中第i层恰用了j种颜色的方案数。因为使用的颜色数不可能多于球数,又总球数不超过10^7,故d[i][j]的状态总数也不超过10^7。

若不考虑两层之间的颜色集合需不同这一条件,则转移方程为

d[i][j] = (m!/(m-j)!) * F[l[i]][j] * Σd[i-1][k]

再减去不符合这一条件的部分即可:

d[i][j] = (m!/(m-j)!) * F[l[i]][j] * Σd[i-1][k] – d[i-1][j] * F[l[i]][j] * j!

其中(m!/(m-j)!)与j!都可以预处理得到

时间复杂度:O(Σl[i] + l[i]^2)

30分

 

100分