HDU 4832 Chess（DP+组合数）

 1 #include<stdio.h>
 2 #include<string.h>
 3 int c[1010][1010];
 4 int dpx[1010][1010],x[1010];
 5 int dpy[1010][1010],y[1010];
 6 int n,m,k,x0,y0;
 7 void init()//求组合数
 8 {
 9     memset(c,0,sizeof(c));
10     for(int i=0;i<1010;i++)
11     {
12         c[i][0]=1;
13         c[i][i]=1;
14         for(int j=1;j<i;j++)
15         {
16             c[i][j]=c[i-1][j-1]+c[i-1][j];
17             while(c[i][j]>=9999991) c[i][j]-=9999991;
18         }
19     }
20     return;
21 }
22 void row()//行的走法
23 {
24     memset(dpx,0,sizeof(dpx));
25     memset(x,0,sizeof(x));
26     dpx[0][y0-1]=1; 
27     x[0]=1;
28     for(int i=1;i<=k;i++)
29         for(int j=0;j<m;j++)
30         {
31             if(j-2>=0) dpx[i][j]+=dpx[i-1][j-2];
32             if(j-1>=0) dpx[i][j]+=dpx[i-1][j-1];
33             if(j+1<m) dpx[i][j]+=dpx[i-1][j+1];
34             if(j+2<m) dpx[i][j]+=dpx[i-1][j+2];
35             while(dpx[i][j]>=9999991) dpx[i][j]-=9999991;
36             x[i]+=dpx[i][j];
37             while(x[i]>=9999991) x[i]-=9999991;    
38         }
39     return;
40 }
41 void colum()//列的走法
42 {
43     memset(dpy,0,sizeof(dpy));
44     memset(y,0,sizeof(y));
45     dpy[0][x0-1]=1; 
46     y[0]=1;
47     for(int i=1;i<=k;i++)
48         for(int j=0;j<n;j++)
49         {
50             if(j-2>=0) dpy[i][j]+=dpy[i-1][j-2];
51             if(j-1>=0) dpy[i][j]+=dpy[i-1][j-1];
52             if(j+1<n) dpy[i][j]+=dpy[i-1][j+1];
53             if(j+2<n) dpy[i][j]+=dpy[i-1][j+2];
54             while(dpy[i][j]>=9999991) dpy[i][j]-=9999991;
55             y[i]+=dpy[i][j];
56             while(y[i]>=9999991) y[i]-=9999991;    
57         }   
58     return;  
59 }
60 int main()
61 {    
62     init();
63     int t;
64     __int64 ans;
65     scanf("%d",&t);
66     for(int p=0;p<t;p++)
67     {
68         scanf("%d %d %d %d %d",&n,&m,&k,&x0,&y0);
69         row();
70         colum();
71         ans=0;
72         for(int i=0;i<=k;i++)//组合相乘累加
73         {
74             ans+=(__int64)c[k][i]*x[i]%9999991*y[k-i]%9999991;
75             ans%=9999991;
76         }
77         printf("Case #%d:\n",p+1); 
78         printf("%d\n",(int)ans);       
79     }
80 }