这题第一想法是矩阵,不过范围太大了,然后就没有思路了。。
之后看到群里的解法,行和列可以分着走,两者是互不影响的,这样就把二维转换成了一维,直接dp求出就可以了。
然后再组合相乘一下。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 1010
#define LL __int64
#define INF 0xfffffff
#define mod 9999991
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
LL dp1[N][N],dp2[N][N];
LL o[][N];
LL c[N][N];
void init()
{
c[][] = ;
for(int i = ;i < ;i++)
{
c[i][] = c[i][i] = ;
for(int j = ; j < i;j++)
{
c[i][j] = c[i-][j] + c[i-][j-];
if(c[i][j] >= mod)
c[i][j] -= mod;
}
}
}
int main()
{
int n,m,t,k,x,y;
int i,j;
int kk = ;
init();
cin>>t;
while(t--)
{
memset(dp1,,sizeof(dp1));
memset(dp2,,sizeof(dp2));
memset(o,,sizeof(o));
scanf("%d%d%d%d%d",&n,&m,&k,&x,&y);
dp1[][x] = ;o[][]+=;
dp2[][y] = ;o[][]+=;
for(i = ;i <=k ;i++)
for(j = ; j <=n ;j++)
{
if(j>) dp1[i][j]=(dp1[i][j]+dp1[i-][j-])%mod;
dp1[i][j]+=dp1[i-][j-];dp1[i][j]%=mod;
dp1[i][j]+=dp1[i-][j+];dp1[i][j]%=mod;
dp1[i][j]+=dp1[i-][j+];dp1[i][j]%=mod;
o[][i]+=dp1[i][j];
o[][i]%=mod;
}
for(i = ; i <=k ;i++)
for(j = ; j <= m ;j++)
{
if(j>) dp2[i][j]+=dp2[i-][j-];dp2[i][j]%=mod;
dp2[i][j]+=dp2[i-][j-];dp2[i][j]%=mod;
dp2[i][j]+=dp2[i-][j+];dp2[i][j]%=mod;
dp2[i][j]+=dp2[i-][j+];dp2[i][j]%=mod;
o[][i]+=dp2[i][j];
o[][i]%=mod;
} LL ans=;
for(i = ; i <= k; i++)
{
ans =(ans+c[k][i]*o[][i]%mod*o[][k-i]%mod)%mod;
}
printf("Case #%d:\n",++kk);
cout<<ans<<endl;
}
return ;
}