题意很简单，告诉你一个矩阵，以及一个起始坐标．

问走k步有多少个不同的路线．

一个路线可以记为上下左右，则k步有k个上下左右，比如 "上上左左下下" 是一个路线．

分析

矩阵的大小是1000*1000, k ＝ １000, 如果使用搜索肯定不行．

起始很容易往矩阵幂这个方向上想，但是状态太多了， 1000*1000 个状态，行不通．

当时我也考虑分行和列来做，但是就差那么一步就不向下想了．

网上找了一个 解题报告 ，这个解题报告的分析很简单，只有一句话： 可以很容易发现行和列是独立的。

好吧！看到这句话我瞬间会做这道题了．

接下来我就具体写写推算公式给大家．

如果是暴力的话，答案应该是

ans = sum( Count(i, j, k) );

对于 Count(i, j, k) 我们怎么求出来呢？

假设 从(x, y) 走 k 步到 坐标(i, j)时, 我们有 t 步是上下移动的， k - t 步是左右移动的，也就是 k 步中有 t 步是上下移动的，及 C(k, t) 吧．

于是我们可以得带这个公式了．

Count(i, j, k) = sum(C(k, t) * Count(i, t) * Count(j, k- t) )

其中 C(k, t) 是组合数

Count(i, t) 代表从数轴x 只上下移动走 t 步到达 数轴 i 的路线数，当然，由于是上下，有个上界n,最大行数.

对应这 Count(j, k-t ) 代表从数轴 y 只左右移动走 k - t 步 到达 j 的路线数， 上界是 m, 最大列数．

我们把这个公式带入暴力公式可以得到

ans = sum( C(k, t) * Count(i, t) * Count(j, k- t)  )

然后我们把 i 展开可以得到

ans = sum(   
C(k, t) * Count(1, t) * Count(j, k- t) 
+C(k, t) * Count(2, t) * Count(j, k- t) 
+ ...
+C(k, t) * Count(n, t) * Count(j, k- t) 
)

ans = sum( C(k, t) * Count(j, k - t) * sum(Count(i, t)) )

ans = sum( 
C(k, t) * Count(1, k - t) * sum(Count(i, t))
＋C(k, t) * Count(2, k - t) * sum(Count(i, t))
＋．．．
＋C(k, t) * Count(m, k - t) * sum(Count(i, t))
 )

这个也可以提取公因式

ans = sum(C(k, t) * sum( Count(j, k-t ) ) * sum( Count( i, t ) ))

对于 Count(i, t) 和 Count(j, k-t ) 我们都可以使用 O(n^2) 的预处理得到．

然后我们再使用O(n) 的预处理可以得到 sum( Count(j, k-t) ) 和 sum( Count(i, t) ).

最后我们使用 O( k ) 的复杂度得到它们的乘积即可．

以上分析来自博文：http://tiankonguse.com/record/record.php?id=667

代码：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define LL long long
#define MOD 9999991
#define MAX 1005

using namespace std;
int map[4]={-2,-1,1,2};
LL C[MAX][MAX];
LL str[2][MAX][MAX];
LL sum[2][MAX];

void GetCount()//预处理C(i,j)获取组合数的值,C(i,j)=C(i-1,j)+C(i-1,j-1);
{
	memset(C,0,sizeof(C));
	C[0][0]=1;
	for(int i=1;i<MAX;i++)
	{
		C[i][0]=C[i][i]=1;
		for(int j=1;j<i;j++)
		{
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
		}
	}
}

void DP(LL str[MAX][MAX],LL sum[MAX],int x,int n,int k)
{
	str[0][x]=1;
	sum[0]=1;
	for(int t=1;t<=k;t++)
	{
		for(int i=2;i<=n;i++)
		{
			for(int j=0;j<4;j++)
			{                  //str[t][i]可能由str[t-1][*]经过四种途径到达
				str[t][i]=(str[t][i]+str[t-1][i+map[j]])%MOD;
			}
			sum[t]=(sum[t]+str[t][i])%MOD;
		}
	}
}

LL Get(int k,int j)
{
	return (((C[k][j]*sum[0][j])%MOD)*sum[1][k-j]%MOD);
}

int main(int argc,char *argv[])
{
	GetCount();
	int t;
	LL ans;
	int n,m,k,x,y;
	scanf("%d",&t);
	for(int i=1;i<=t;i++)
	{
		scanf("%d%d%d%d%d",&n,&m,&k,&x,&y);
		n++;
		m++;
		x++;
		y++;
		memset(str,0,sizeof(str));
		memset(sum,0,sizeof(sum));
		DP(str[0],sum[0],x,n,k);
		DP(str[1],sum[1],y,m,k);
		ans=0;
		for(int j=0;j<=k;j++)
			ans=(ans+Get(k,j))%MOD;
		printf("Case #%d:\n%I64d\n",i,ans);
	}
	return 0;
}