CF140E New Year Garland (计数问题)
用$m$种颜色的彩球装点$n$层的圣诞树。圣诞树的第$i$层恰由$a_{i}$个彩球串成一行,且同一层内的相邻彩球颜色不同,同时相邻两层所使用彩球的颜色集合不 同。求有多少种装点方案,答案对$p$取模。
好神的计数问题,zwz Orz
题解思路来自黄学长hzwer的博客
先只考虑在一行内的彩球的方案数
定义$g[i][j]$表示一共有$i$个球串成一行,一共用了$j$种颜色的方案数
因为所有颜色都是等价的,我们可以利用最小表示法来简化计数,比如让颜色编号为$x+1$的球第一次出现的位置,在颜色编号为$x$的球之前。实际的方案数是$g[i][j]\cdot j!$
这样递推关系就简单多了
加入一个新颜色的球,$g[i][j]+=g[i-1][j-1]$
加入一个旧颜色的球,颜色不能和第$i-1$个球相同,$g[i][j]+=(j-1)g[i-1][j]$
$g[i][j]=g[i-1][j-1]+(j-1)g[i-1][j]$
在考虑行行之间的影响
定义$f[i][j]$表示前$i$行,其中第$i$行选了$j$种颜色的方案数
如果没有相邻两行集合不同这种限制
$f[i][j]=C_{m}^{j}\cdot g[a_{i}][j]\cdot \sum f[i-1][k]$
如果加上限制,
$f[i][j]=C_{m}^{j}\cdot g[a_{i}][j]\cdot j!\sum f[i-1][k]-g[a_{i}][j]\cdot j!\cdot f[i-1][j]$
$=A_{m}^{j}\cdot g[a_{i}][j]\sum f[i-1][k]-g[a_{i}][j]\cdot j!\cdot f[i-1][j]$
利用前缀和优化可以$O(1)$转移
$f[i][j]$的状态数也仅仅是$O(\sum a_{i})$,用滚动数组记录
$A_{m}^{j}$和$j!$可以通过预处理得到
总结:由于本题的模数是非质数,用组合数计数会让问题变得复杂,且时间复杂度很难保证。如果本题保证模数为质数,可能会有很多其他做法,比如组合数+容斥等等,但应该都没有官方题解的思路简洁。出题者似乎引导我们走向突破口——消去组合数,突破口在于通过化简,把组合数化成排列数和阶乘,排列数和阶乘即使在模数为非质数的情况下,也能在$O(n)$时间预处理
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N1 5010
#define M1 1000010
#define dd double
#define ll long long
using namespace std; int gint()
{
int ret=,fh=;char c=getchar();
while(c<''||c>''){if(c=='-')fh=-;c=getchar();}
while(c>=''&&c<=''){ret=ret*+c-'';c=getchar();}
return ret*fh;
}
int n,m,mx,P; int f[][N1],g[N1][N1],am[N1],mul[N1],a[M1]; int main()
{
int i,j,x;
scanf("%d%d%d",&n,&m,&x);
for(i=;i<=n;i++) scanf("%d",&a[i]), mx=max(mx,a[i]);
const int p=x;
g[][]=g[][]=;
for(i=;i<=mx;i++) for(j=;j<=i;j++) g[i][j]=(1ll*(j-)*g[i-][j]%p+g[i-][j-])%p;
mul[]=mul[]=; am[]=;
for(i=;i<=min(m,mx);i++) am[i]=1ll*am[i-]*(m-i+)%p;
for(i=;i<=mx;i++) mul[i]=1ll*mul[i-]*i%p;
int now=,pst=,snow=,spst=;
f[pst][]=;
for(i=;i<=n;i++)
{
snow=;
for(j=;j<=min(m,a[i]);j++)
f[now][j]=(1ll*am[j]*g[a[i]][j]%p*spst%p-1ll*f[pst][j]*mul[j]%p*g[a[i]][j]%p+p)%p, (snow+=f[now][j])%=p;
memset(f[pst],,(min(m,a[i-])+)<<);
swap(now,pst); swap(snow,spst);
}
printf("%d\n",spst);
return ;
}
最新文章
- 高性能MySQL(三):服务器性能剖析
- 基于HTML5的Web SCADA工控移动应用
- vijos1907[noip2014]飞扬的小鸟(完全背包)
- noi 2718 移动路线
- iOS开发——高级技术&;内购服务
- ArcGIS中定义图框样式
- PHP数组的一些常用函数
- Spring中使用log4j随笔
- 解决Admob Banner首次展示不显示的问题
- 关于default的位置问题:default放在前面
- Shell实例----------从文件夹里面多个文件里面查找指定内容
- JS基础四
- 再回首UML之下篇
- mysql 无法插入中文
- Docker的使用初探(一):常用指令说明
- eDEX-UI
- NOIP2011提高组 选择客栈
- Luogu4040 AHOI/JSOI2014 宅男计划 贪心、二分、三分
- socket网络编程扫盲篇
- linux_shell_数组