【CQOI2011】放棋子
在一个n行m列的棋盘里放一些彩色的棋子,使得每个格子最多放一个棋子,且不同颜色的棋子不能在同一行或者同一列。有多少种方法? 例如\(,n=m=3\),有两个白棋子和一个灰棋子,下面左边两种方法都是合法的,但右边两种都是非法的。
输出答案对\(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<