描述
给定n, m。一个n × m矩阵是好矩阵当且仅当它的每个位置都是非负整数，且每行每列的和 ≤ 2。求好矩阵的个数，模109 + 7
输入
第一行一个整数T，表示测试点个数。下面T个测试点。每个测试点一行，包含两个整数n，m。1 ≤ T ≤ 104. 1 ≤ n, m ≤ 100.
输出
T行。每行是对应测试点的答案。
样例输入
1 2 2
样例输出
26
应该算是比较常规的DP题，有点卡时。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=110; const int mod=1000000007; typedef long long ll; ll f[maxn][maxn][maxn],g[maxn][maxn][maxn],ans[maxn][maxn]; //前若干行，现在共有i列和为0，j列和为1，k列和为2的方案数 int main() { rep(i,0,100) f[i][0][0]=1; rep(n,1,100) { rep(i,0,100) rep(j,0,100-i) rep(k,0,100-i-j) g[i][j][k]=f[i][j][k],f[i][j][k]=0; rep(i,0,100) rep(j,0,100-i) rep(k,0,100-i-j) if(g[i][j][k]) { ll res=g[i][j][k]; f[i][j][k]+=res;//without putting if(i>=1) f[i-1][j+1][k]+=res*i;//put a 1 if(j>=1) f[i][j-1][k+1]+=res*j; if(i>=1&&j>=1) f[i-1][j][k+1]+=res*i*j;//put double 1 if(i>=2) f[i-2][j+2][k]+=res*i*(i-1)/2; if(j>=2) f[i][j-2][k+2]+=res*j*(j-1)/2; if(i>=1) f[i-1][j][k+1]+=res*i;//put a 2 } rep(i,0,100) rep(j,0,100-i) rep(k,0,100-i-j) { f[i][j][k]%=mod; (ans[n][i+j+k]+=f[i][j][k])%=mod; } } int T=read(); while(T--) { int n=read(),m=read(); printf("%lld ",ans[n][m]); } return 0; }