bzoj 3294:[Cqoi 2011]放駒(反発原理+組合せ数+DP)

タイトルの説明
トランスファゲート
1つのn*mの碁盤の中でいくつかの色の異なる駒を入れて、各格子は最大で1つの駒しか置くことができなくて、異なる色の駒は同じ行あるいは同じ列に置くことができなくて、合法的な方案の数を求めます.
問題解
行ごとに列ごとに1つの色しか占められないことに相当します.では、各色に行列数を割り当てることができます.g[p][i][j]は、p番目の色がi行j列を占めるシナリオ数を表す.gを求めることができれば、二次元リュックサックを作ることができます.f[t][i+k][j+l]+=f[t−1][i][j]∗g[t][k][l]∗C[n−i][k]∗C[m−j][l]がどのようにgを求めるか、直接組み合わせ数で算出されたスキームに空行や空列が存在する可能性があるので、反発を許さなければならない.g[p][i][j]=C[i∗j][c]−C[i][x]∗C[j][y]∗g[p][x][y]ここでx,yはi,jに同時に等しくない.
コード#コード#

#include
#include
#include
#include
#include
#define N 33
#define LL long long 
#define p 1000000009
using namespace std;
LL C[1003][1003],g[N][N][N],f[N][N][N];
int n,m,k;
int main()
{
    freopen("a.in","r",stdin);
    scanf("%d%d%d",&n,&m,&k);
    for (int i=0;i<=1000;i++) C[i][0]=1;
    for (int i=1;i<=1000;i++)
     for (int j=1;j<=i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%p;
    for (int t=1;t<=k;t++) {
        int c; scanf("%d",&c);
        for (int i=0;i<=n;i++)
         for (int j=0;j<=m;j++) {
            g[t][i][j]=C[i*j][c];
            for (int k=0;k<=i;k++)
             for (int l=0;l<=j;l++) 
              if (k!=i||l!=j) g[t][i][j]=(g[t][i][j]-C[i][k]*C[j][l]%p*g[t][k][l]%p)%p;
         }
    }
    f[0][0][0]=1;
    for (int t=1;t<=k;t++)
     for (int i=0;i<=n;i++)
      for (int j=0;j<=m;j++)
       for (int k=0;k<=n;k++)
        for (int l=0;l<=m;l++)
         if (i+k<=n&&j+l<=m) {
            f[t][i+k][j+l]+=f[t-1][i][j]*g[t][k][l]%p*C[n-i][k]%p*C[m-j][l]%p;
            f[t][i+k][j+l]%=p;
         } 
    LL ans=0;
    for (int i=0;i<=n;i++)
     for (int j=0;j<=m;j++) ans=(ans+f[k][i][j])%p;
    printf("%I64d
",(ans%p+p)%p);
}