本文主要是介绍hihocoder 1124 : 好矩阵 dp,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
好矩阵
-
1 2 2
样例输出 -
26
描述
给定n, m。一个n × m矩阵是好矩阵当且仅当它的每个位置都是非负整数,且每行每列的和 ≤ 2。求好矩阵的个数,模109 + 7
输入
第一行一个整数T,表示测试点个数。下面T个测试点。每个测试点一行,包含两个整数n,m。1 ≤ T ≤ 104. 1 ≤ n, m ≤ 100.
输出
T行。每行是对应测试点的答案。
题意很简单,由于,数量很大,如果考虑一个一个方格的放,要考虑横向的,又要考虑竖向的,很复杂,所以不可取。所以一排一排的放,如果,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 1000000007
int 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<n;i++){for(int a = 0;a<=m;a++){for(int b = 0;a + b<=m;b++){dp[i+1][a][b]+= dp[i][a][b];dp[i+1][a][b] %= MOD;if(a >= 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;
}
这篇关于hihocoder 1124 : 好矩阵 dp的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!