题意:给了n*m的网格,然后有p个重型的防御塔,能承受1次攻击,q个轻型防御塔不能接受任何攻击,然后每个防御搭会攻击他所在的行和所在的列,最后求在这个网格上放至少一个防御塔的方案数,
我们枚举 选取多少个重型防御塔然后这个重型防御塔有多少是两个在一行,和两个在一列 O(P^3)的效率
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string.h>
#include <vector>
using namespace std;
typedef long long LL;
const LL MOD=;
const int maxn=;
LL C[maxn][maxn];//组合数
LL light[maxn][maxn][maxn];// light[i][j][k]k栈轻量级的防御塔放在i行j列的矩阵的方案数
LL heavy[maxn];// haeavy[i] 表示有i个两个同一行的重量级的方案数
LL Nt[maxn];//N! n阶乘
void init()
{
Nt[]=;
for(LL i=; i<=; i++)
Nt[i]=(Nt[i-]*i)%MOD;
memset(C,,sizeof(C));
C[][]=;
for(int i=; i<=; i++)
{
C[i][]=;
for(int j=; j<=i; j++)
C[i][j]=(C[i-][j]+C[i-][j-])%MOD;
}
for(int i=; i<=; i++)
for(int j=; j<=; j++)
{
int kM=min(i,j);
light[ i ][ j ][ ] = ;
for(int k=; k<=kM; k++)
{
light[ i ][ j ][ k ]=( ( (C[ i ][ k ]*C[ j ][ k ])%MOD )*Nt[k])%MOD;
}
}
for(int i=; i<=; i++)
for(int j=; j<=; j++)
{
int kM=min(i,j);
for(int k=; k<=kM; k++)
light[i][j][k]=(light[i][j][k-]+light[i][j][k])%MOD;
}
heavy[]=;
for(int i=; i<=; i++)
{
LL ans=;
for(int j=i*; j>; j-= )
{
ans=(C[j][]*ans)%MOD;
}
heavy[i]=ans;
}
}int main()
{
init();
int N,M,P,Q;
int cas;
scanf("%d",&cas);
for(int cc=; cc<=cas; cc++)
{
scanf("%d%d%d%d",&N,&M,&P,&Q);
LL ans=;
for(int k=; k<=P; k++)
for(int i=; i<=k; i+=)
for(int j=; j+i<=k; j+=)
{
int LN=N-i/-j;
int LM=M-j/-i;
if(min(LN,LM)<k-(i+j) )continue;
LN=N,LM=M;
LL d=;
d=( ( ( C[LN][i/]*C[LM][i] )%MOD )*heavy[i/])%MOD;
LN-=i/; LM-=i;
d=( d*( ( ( ( C[LN][j] * C[LM][j/] )%MOD ) * heavy[j/] )%MOD ) )%MOD;
LN-=j;
LM-=j/;
int lest=k-(i+j);
d= ( ( ( d*( ( C[LN][lest]*C[LM][lest] )%MOD ))%MOD)*Nt[lest] )%MOD;
LN-=lest;LM-=lest;
if(LN>&&LM>)
{
int ge=min(min(LN,LM),Q);
d=(d*(light[LN][LM][ge]))%MOD;
}
ans=(ans+d)%MOD;
}
if(Q>)
{
int ge=min(min(N,M),Q);
ans=(ans+light[N][M][ge])%MOD;
ans=(ans-+MOD)%MOD;
}
printf("%I64d\n",ans%MOD);
}
return ;
}