• 有一个R行C列的棋盘。“皇后”的每一步走法是可以从当前所在的格子走到同一行的任意一个格子、同一列的任意一个格子、所在的两条对角线的任何一个格子。“非皇后”的每一步走法与“皇后”的走法刚好相反，凡是“皇后”能走到的格子，“非皇后”都不能走；凡是“皇后”不能走的格子，“非皇后”都能走。

• 现在你要把一个棋子放到棋盘的任意一个格子，然后该棋子每一步都要按照“非皇后”的走法，恰好走N步，注意每一步都要走，不能停留。把该棋子经过的这\(N+1\)个格子看是一个排列，就得到一种方案。问有多少种不同的合法方案。答案模\(1000000007\)。

• \(1 \leq R,C,N \leq 200\)

• 限时：\(2s\)

---

看到这道题，可以马上想到\(DP\)

开一个数组\(f[i][j][k]\)，\(i\)表示现在枚举到第\(i\)行，\(j\)表示现在枚举到第\(j\)列，\(k\)表示现在走了第\(k\)步。

因为刚开始棋子可以摆在任意位置，所以\(f[i][j][0]\)都为\(1\)。

---

• 先从最简单的入手\(\Longrightarrow\) 假如棋子是按皇后的走法

对于一个格子，他可以从同行、同列格子转移而来，他还可以从同对角线的格子而来

时间复杂度：\(O(n^4)\)

---

• 接着思考\(\Longrightarrow\) 假如棋子是按非皇后的做法

在上面讲过，若棋子是按皇后的走法，一个格子是由同行、同列、同对角线转移而来。而棋子若是按皇后的走法，一个格子就不是由同行、同列、同对角线转移而来。这恰好是相反关系。相当于我们只要用全部可转移方案减去皇后走法的实际转移结果。

\(f[i][j][k]=\sum\limits_{p=1}^C\sum\limits_{q=1}^Cf[p][q][k-1]-f[i][j][k]\)

时间复杂度：\(O(n^4)\)

---

• 优化

虽然目前的时间复杂度\(O(n^4)\)，但是\(200^4\)依旧十分庞大，肯定有些数据点会\(TLE\)。

我们发现我们程序唯一做的重复操作便是第一步，也就是统计棋子按皇后走法方案

比如说在\(f[i][j][k]\)这个节点，他可以从同行的格子转移而来，而\(f[i][j+1][k]\)这个节点也能从同行的格子转移而来。显然两次操作有所重复，这时我们只要用到部分和便可以优化时间了。

优化后时间复杂度： \(O(n^3)\)

---

上代码

#include<bits/stdc++.h>
using namespace std;
int R,C,n,b,c;
long long h[205],l[205],zx[405],yx[205][205],f[205][205][205];
const int MOD=1000000007;
long long sum,ans;
int main()
{
  scanf("%d%d%d",&R,&C,&n);
  for(int i=1; i<=R; i++)
    for(int j=1; j<=C; j++)
      f[i][j][0]=1;
  for(int i=1; i<=n; i++)
  {
  	sum=0;
  	for(int j=1; j<=R; j++)h[j]=0;
	for(int j=1; j<=C; j++)l[j]=0;  
	for(int j=2; j<=R+C; j++)zx[j]=0;
	for(int j=1; j<=C; j++) yx[1][j]=0;
	for(int j=2; j<=R; j++) yx[j][1]=0;
	for(int j=1; j<=C; j++){b=1;c=j;while(b<=R&&c<=C) yx[1][j]=(yx[1][j]+f[b][c][i-1])%MOD,b++,c++;}
	for(int j=2; j<=R; j++){b=j;c=1;while(b<=R&&c<=C) yx[j][1]=(yx[j][1]+f[b][c][i-1])%MOD,b++,c++;}
  	for(int j=1; j<=R; j++)
	  for(int k=1; k<=C; k++)
	  h[j]=(h[j]+f[j][k][i-1])%MOD;
	for(int j=1; j<=R; j++)
	  for(int k=1; k<=C; k++)
	  l[k]=(l[k]+f[j][k][i-1])%MOD;
	for(int j=2; j<=R+C; j++)
	{
	  b=1; c=j-b;
	  while(c>C) b++,c--;
	  while(c>0&&b<=R)zx[j]=(zx[j]+f[b][c][i-1])%MOD,b++,c--;
	}
    for(int j=1; j<=R; j++)
	  for(int k=1; k<=C; k++)
	  {
	  	sum+=f[j][k][i-1];
	  	f[j][k][i]=(f[j][k][i]+l[k]-f[j][k][i-1])%MOD;
	  	f[j][k][i]=(f[j][k][i]+h[j]-f[j][k][i-1])%MOD;
	  	f[j][k][i]=(f[j][k][i]+yx[j-min(j,k)+1][k-min(j,k)+1]-f[j][k][i-1])%MOD;
	  	f[j][k][i]=(f[j][k][i]+zx[j+k]-f[j][k][i-1])%MOD;
	  }
	for(int j=1; j<=R; j++)
	  for(int k=1; k<=C; k++)
	  f[j][k][i]=(sum-f[j][k][i-1]-f[j][k][i])%MOD;
  }
  for(int i=1; i<=R; i++)
    for(int j=1; j<=C; j++) ans=(ans+f[i][j][n])%MOD;
  cout<<ans;
  return 0;
}