codeforces 140E.New Year Garland
传送门:
解题思路:
要求相邻两行小球颜色集合不同,并且限制行内小球相邻不同。
由此可得:每行小球排列都是独立与外界的,
所以答案应该是对于所有行的颜色集合分类,在将行内的答案乘到上面。
先考虑如何分类:
我们可以确定对于每行所取的颜色种类$x=|S|$,
若相邻两行$i,j$,其$x_i!=x_j$,那么一定是合法的,有$C_m^x$种选择方法。
而对于相邻两行$x_i=x_j$,对于行$i$的一种方案,只有一种可能使得$S_i=S_j$,
所以可以使用容斥来计算答案
综上所述,按照每行的颜色种类数来分类或许是可行的。
所以说我们表示出答案:
设该行共用$x$种颜色的方案数为$f(x)$,$f(x)$是对于所有的种类进行计数的,所以可以直接与颜色数为$x$的其他计数变量相乘,设第$n$行中颜色为$i$对整体的贡献为$ans_{n,i}$则:
$ans_n=C_m^x*f(x)*ans_{n-1}-f(x)*ans_{n-1,j}$
$ans_n=\sum\limits_{c=1}^{l_n}ans_{n,c}$
用函数$g_{i,j}$表示就是$ans_i=\sum g_{i,j}$表示前$i$行中最后一行用$j$个颜色方案数。
行间计数搞定了,就该考虑如何计算$f(x)$
由于刚才设$f(x)$为该行的方案数。这个看起来不太好求。
考虑什么决定了这个方案数。
是该行的球数以及颜色数。
所以不妨改写一下,$f(i,j)$表示用了$i$个球,共$j$种颜色的方案数,那么第$i$行的$f(x)$重写为$f(l_i,x)$
考虑一个一个来添加球,由于要求和前一个颜色不同,即可获得递推式:
$f(i,j)=f(i-1,j-1)+f(i-1,j)*(j-1)$
由于每次用到没有用过的颜色顺序是有序的,而所求的是对球颜色顺序无要求,那么最后使用的时候应写成:
$j!*f(i,j)$
球颜色数不会多于总数,那么$f(i,j)$,可以用二维数组来储存
最后一个问题就是p不是质数不能直接用逆元。
难不成要用拓展Lucas?
组合数可以提出来:
那么答案就是:
$g_{i,j}=A_{m}{j}*f(i,j)*\sum{g_{i-1}}-j!*f(i,j)*g_{i-1,j}$
其中$f_{(i,j)},j!,A_m^j$预处理就可以很愉快地A掉这道题目了
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
typedef long long lnt;
lnt n,m,p;
lnt lmax;
lnt Am[];
lnt fac[];
lnt l[];
lnt f[][];
lnt g[][];
int main()
{
scanf("%lld%lld%lld",&n,&m,&p);
fac[]=Am[]=f[][]=;
for(int i=;i<=n;i++)
scanf("%lld",&l[i]),lmax=std::max(lmax,l[i]);
for(int i=;i<=lmax;i++)Am[i]=Am[i-]*(m-i+)%p;
for(int i=;i<=lmax;i++)fac[i]=fac[i-]*i%p;
for(int i=;i<=lmax;i++)for(int j=;j<=i&&j<=m;j++)
f[i][j]=(f[i-][j-]+f[i-][j]*(j-))%p;
lnt ans=,sum=;
for(int i=;i<=n;i++)
{
for(int j=;j<=l[i];j++)
{
lnt tmp=(Am[j]*ans-g[i&^][j]*fac[j])%p;
g[i&][j]=f[l[i]][j]*tmp%p;
sum+=g[i&][j];
}
ans=(sum%p+p)%p;
sum=;
memset(g[i&^],,sizeof(g[]));
}
printf("%lld\n",ans);
return ;
}
最新文章
- 20145212——GDB调试汇编堆栈过程分析
- 安装OS X虚拟机错误vcpu-0:VERIFY vmcore/vmm/main/physMem_monitor.c:1123
- 小学徒成长系列—StringBuilder &; StringBuffer关键源码解析
- linux hadoop安装
- EMC Documentum DQL整理(一)
- python 杨辉三角
- Memcached 分布式缓存实现原理
- Github 恶搞教程(一起『玩坏』自己的 Github 吧)
- ORA-12505, TNS:listener does not currently know of SID given in connect descriptor (二)
- JLink 在J-Flash ARM批处理自动下载
- sublime 安装 Terminal 使用 cmder
- 支付宝集成SDK 报错
- StringBuilder[] 作为数组如何使用
- Android学习之菜单
- SQL1-(增删改查、常用函数)
- Ubuntu常用软件推荐,图文详细说明及下载
- hdoj 1506&;amp;&;amp;1505(City Game) dp
- windows 常用操作
- 【算法与数据结构】Java实现字符串的全排列及组合
- C#下载Url文件到本地