NOIP 罕见的考了计数问题。

大意 填一个 n × m 的 对于所有数据 n ≤ 8, m ≤ 1000000。 目做法： n 很小，猜测应该是状态压缩 DP，首先暴力。设 F (n, m) 是 n, m 的答案。 发现 n 确定的情况下，当 m ≥ n + 2 时，F (n, m) = 3F (n, m − 1)。所以难点在于暴力比较小的部分。 暴力主要分为两部分，枚举和验证。 枚举部分，注意到右上到左下斜线上一定是单调不降的（先一些 0 再一些 1。） 利用这个可以极大的减少需要计算的状态。 然后考虑验证的问题，一共走的步数很少（比如 20 步） 可以用一个 int 类型来存这个 01 串。 对于每个点计算，从当前点到终点，字串最大是多少，最小是多少。 对于不在最后一行最后一列的点，都要保证右边的最大小于等于下边的最小。 参考代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int mo=1e9+7;
int n,m,d[100][100];
int f[10001][50],g[10001][50];
int Solve()
{
for (int i=0; i<(1<<n); i++) f[i][n]=1;
for (int i=2; i<=m; i++)
{
for (int j=0; j<(1<<n); j++)
for (int k=1; k<=n; k++) g[j][k]=0;
for (int j=0; j<(1<<n); j++)
{
for (int k=1; k<=n; k++)
{
if (f[j][k]==0) continue;
for (int k2=0; k2<(1<<n); k2++)
{
bool judge=1;
for (int k3=1; k3<n; k3++)
{
bool j1=(k2&(1<<(k3-1)));
bool j2=(j&(1<<k3));
if (j1>j2)
{
judge=0;
break;
}
if (j1==j2&&k3>k)
{
judge=0;
break;
}
}
if (!judge) continue;
int max0=1;
for (int k3=1; k3<n; k3++)
{
bool j1=(k2&(1<<(k3-1)));
bool j2=(j&(1<<k3));
if (j1!=j2) break;
max0=k3+1;
if (k3+1>=k) break;
}
max0=min(max0,k);
g[k2][max0]=(g[k2][max0]+f[j][k])%mo;
}
}
}
for (int j=0; j<(1<<n); j++)
for (int k=1; k<=n; k++) f[j][k]=g[j][k];
}
int ans=0;
for (int i=0; i<(1<<n); i++)
for (int j=1; j<=n; j++) ans=(ans+f[i][j])%mo;
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
if (n>m) swap(n,m);
if (n==1)
{
int now=1;
for (int i=1; i<=m; i++) now=now*2%mo;
cout<<now<<endl;
return 0;
}
if (n==m)
{
int ans=Solve();
cout<<ans<<endl;
return 0;
}
int km=m;
m=n+1;
int ans=Solve();
for (int i=n+2; i<=km; i++) ans=(ans*2%mo+ans)%mo;
cout<<ans<<endl;
return 0;
}