tyvj4541 zhx 提高组P1

背景

提高组

描述

在一个N×M的棋盘上，要求放置K个车，使得不存在一个车同时能被两个车攻击。问方案数。

输入格式

一行三个整数，N,M,K。

输出格式

一行一个整数，代表答案对1000001取模之后的值。

备注

【样例输入1】
4 5 2
【样例输出1】
190
【样例输入2】
2 3 3
【样例输出2】
6
【样例输入3】
6 7 20
【样例输出3】
0
【样例输入4】
23 37 39
【样例输出4】
288688
【样例解释】
【数据规模与约定】
对于100%的数据，1≤N,M≤50,1≤K≤100。

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn = ,mod = ;

int n,m,k,f[][maxn<<][maxn<<][maxn<<],ans,cnt;

int main(){

    cin>>n>>m>>k;

    f[][][][] = ;

    for(int i = ;i <= n;i++){

        cnt ^= ;

        for(int j = ;j <= n<<;j++){

            for(int l = ;l <= n<<;l+=){

                for(int p = ;p <= n;p++){

                    f[cnt][j][l][p] = f[cnt^][j][l][p];

                    if(j > ) f[cnt][j][l][p] += f[cnt^][j-][l][p]*(m-j-p-l+);

                    if(p > ) f[cnt][j][l][p] += f[cnt^][j+][l][p-]*(j+);

                    if(l > ) f[cnt][j][l][p] += (f[cnt^][j][l-][p]*(m-j-l-p+)*(m-j-l-p+))>>;

                    f[cnt][j][l][p] %= mod;

                    if(i == n && j + l + (p<<) == k){

                        ans = (ans + f[cnt][j][l][p]) % mod;

                    }

                }

            }

        }

    }

    cout<<ans;

    return ;

}