好矩阵
时间限制: 3000ms
单点时限: 1000ms
内存限制: 256MB
描写叙述
给定n, m。一个n × m矩阵是好矩阵当且仅当它的每一个位置都是非负整数，且每行每列的和 ≤ 2。求好矩阵的个数。模109 + 7
输入
第一行一个整数T，表示測试点个数。
以下T个測试点。
每一个測试点一行。包括两个整数n。m。
1 ≤ T ≤ 104. 1 ≤ n, m ≤ 100.
输出
T行。
每行是相应測试点的答案。
12 2例子输出
26
题意非常easy。因为，数量非常大。假设考虑一个一个方格的放，要考虑横向的，又要考虑竖向的，非常复杂，所以不可取。所以一排一排的放，假设，m是一定的，那么。每一排仅仅须要考虑不超过2，且与前面已经排好的不冲突就能够了。
dp[i][a][b]表示，第i排，有a列0，b列1，m - a - b列2，的个数则
dp[i+1][a][b]+= dp[i][a][b];//第i+1排全放0
dp[i+1][a-1][b] += (ll)a * dp[i][a][b];//第i+1排在和为0那些列放一个2 dp[i+1][a-1][b+1] += (ll)a * dp[i][a][b];//第i+1排和为1放一个1 dp[i+1][a-1][b]+= (ll)a * (ll) b * dp[i][a][b];//第i+1排和为0 和为1的列各选一个 放两个1 dp[i+1][a][b-1] += (ll)b * dp[i][a][b];//第i+1排选一个和为1的列放一个1 dp[i+1][a-2][b+2] += (ll)(a * (a-1)/2) * dp[i][a][b];//第i+1排选两个和为0放两个1 dp[i+1][a][b-2] += (ll)(b * (b-1)/2) * dp[i][a][b];//第i+1排选两个和为1的放两个1总复杂度为o(n^4);
#define N 105#define M 100005#define maxn 205#define MOD 1000000007int n,m,T;ll dp[N][N][N],ans[N][N];int main(){ //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); for(int m = 1;m<=100;m++){ int n = 100; for(int i =0;i<=n;i++){ for(int a = 0;a<=m;a++){ for(int b = 0;b<=m;b++){ dp[i][a][b] = 0; } } } dp[0][m][0] = 1; for(int i = 0;i = 1){ dp[i+1][a-1][b] += (ll)a * dp[i][a][b]; dp[i+1][a-1][b] %= MOD; dp[i+1][a-1][b+1] += (ll)a * dp[i][a][b]; dp[i+1][a-1][b+1] %= MOD; } if(a >= 1 && b >= 1){ dp[i+1][a-1][b]+= (ll)a * (ll) b * dp[i][a][b]; dp[i+1][a-1][b] %= MOD; } if(b >= 1 ){ dp[i+1][a][b-1] += (ll)b * dp[i][a][b]; dp[i+1][a][b-1] %= MOD; } if(a >= 2 ){ dp[i+1][a-2][b+2] += (ll)(a * (a-1)/2) * dp[i][a][b]; dp[i+1][a-2][b+2] %= MOD; } if(b >= 2 ){ dp[i+1][a][b-2] += (ll)(b * (b-1)/2) * dp[i][a][b]; dp[i+1][a][b-2] %= MOD; } } } ans[i+1][m] = 0; for(int a = 0;a<=m;a++){ for(int b = 0;b<=m;b++){ ans[i+1][m] += dp[i+1][a][b]; ans[i+1][m] %= MOD; } } } } while(S(T)!=EOF) { while(T--){ int s,e; S2(s,e); printf("%lld\n",ans[s][e]); } } return 0;}