博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【CQOI2011】放棋子
阅读量:5810 次
发布时间:2019-06-18

本文共 2395 字,大约阅读时间需要 7 分钟。

【CQOI2011】放棋子

  在一个n行m列的棋盘里放一些彩色的棋子,使得每个格子最多放一个棋子,且不同颜色的棋子不能在同一行或者同一列。有多少种方法? 例如\(,n=m=3\),有两个白棋子和一个灰棋子,下面左边两种方法都是合法的,但右边两种都是非法的。

  img  img

输出答案对\(10^9+9\)取模的结果。

我们设\(f_{i,j,k}\)表示前\(i\)种颜色的棋子,占了\(j\)\(k\)列的方案数。

转移时,考虑第\(i\)种颜色占了\(j'\)\(k'\)列的方案数为\(g_{i,j',k'}\)

\[ \displaystyle f_{i,j,k}=\sum f_{i-1,j-j',k-k'}\cdot g_{i,j',k'}\cdot \binom{n-j+j'}{j'}\cdot \binom{m-k+k'}{k'} \]
考虑求\(g_{i,j',k'}\)

我们求出最多占了\(j'\)\(k'\)列的方案数为\(h_{i,j',k'}\)\(h_{i,j',k'}=\binom{j'\cdot k'}{c_i}\)\(c_{i}\)就是第\(i\)种颜色的棋子数量。然后容斥一下就好了。

代码:

#include
#define ll long long#define N 35#define C 15using namespace std;inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}const ll mod=1e9+9;ll ksm(ll t,ll x) { ll ans=1; for(;x;x>>=1,t=t*t%mod) if(x&1) ans=ans*t%mod; return ans;}int n,m,q;int size[C];ll f[N][N][C];ll g[N][N];ll fac[N*N],ifac[N*N];ll c(int n,int m) {return fac[n]*ifac[m]%mod*ifac[n-m]%mod;}void pre(int now) { for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(i*j>=size[now]) g[i][j]=c(i*j,size[now]); } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { for(int q=1;q<=i;q++) { for(int k=1;k<=j;k++) { if(q==i&&k==j) continue ; g[i][j]=(g[i][j]-g[q][k]*c(i,q)%mod*c(j,k)%mod+mod)%mod; } } } }}int main() { n=Get(),m=Get(),q=Get(); fac[0]=1; for(int i=1;i<=n*m;i++) fac[i]=fac[i-1]*i%mod; ifac[n*m]=ksm(fac[n*m],mod-2); for(int i=n*m-1;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod; for(int i=1;i<=q;i++) size[i]=Get(); f[0][0][0]=1; for(int i=1;i<=q;i++) { memset(g,0,sizeof(g)); pre(i); for(int j=0;j<=n;j++) { for(int k=0;k<=m;k++) { if(!f[j][k][i-1]) continue ; for(int j2=j+1;j2<=n;j2++) { for(int k2=k+1;k2<=m;k2++) { if(!g[j2-j][k2-k]) continue ; (f[j2][k2][i]+=f[j][k][i-1]*g[j2-j][k2-k]%mod*c(n-j,j2-j)%mod*c(m-k,k2-k))%=mod; } } } } } ll ans=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) (ans+=f[i][j][q])%=mod; cout<

转载于:https://www.cnblogs.com/hchhch233/p/10520719.html

你可能感兴趣的文章
iOS - UIViewController
查看>>
IntPtr 转 string
查看>>
学生名单
查看>>
(转) 多模态机器翻译
查看>>
【官方文档】Nginx负载均衡学习笔记(三) TCP和UDP负载平衡官方参考文档
查看>>
矩阵常用归一化
查看>>
Oracle常用函数总结
查看>>
【聚能聊有奖话题】Boring隧道掘进机完成首段挖掘,离未来交通还有多远?
查看>>
USNews大学排名遭美国计算机研究学会怒怼,指排名荒谬要求撤回
查看>>
struts1——静态ActionForm与动态ActionForm
查看>>
七大关键数据 移动安全迎来历史转折点
查看>>
在AngularJS中学习javascript的new function意义及this作用域的生成过程
查看>>
盘点物联网网关现有联网技术及应用场景
查看>>
1、下载安装scala编译器(可以理解为scala的jdk),地址:http://www.scala
查看>>
mui 总结2--新建第一个app项目
查看>>
nginx的lua api
查看>>
考研太苦逼没坚持下来!看苑老师视频有点上头
查看>>
HCNA——RIP的路由汇总
查看>>
zabbix监控php状态(四)
查看>>
定时任务的创建
查看>>