首页 > 代码库 > zoj - 3538（矩阵乘法）
zoj - 3538（矩阵乘法）
题目链接：here——————
题意：有四个人 A,B,C,D 每天出一套卷子，相邻的两天不能由同一个人出题
给你两个数n，m分别表示n天和m个操作（把第ai天定为有bi出题）
问有多少种方式？？
题解： 先排序
if bi == bi-1 && ai - ai-1 = 1 return 0;
if bi == bi-1 设f1 = 3；fn = 3^n - fn-1;
else f1 = 2;fn = 3^n - fn-1;
再判断两头
矩阵 -1,0
3,3
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 typedef long long LL; 7 const LL mod = 1000000007; 8 struct Z{ 9 LL m[2][2];10 LL a;11 string b;12 }s[20];13 Z A ={14 -1,0,15 3,316 };17 Z B = {18 1,0,19 0,120 };21 LL Pow(LL a,LL b){22 LL res = 1;23 while(b){24 if(b&1) res = res * a % mod ;25 a = a * a % mod;26 b >>= 1;27 }28 return res;29 }30 bool cmp(Z p,Z q){31 return p.a < q.a;32 }33 Z operator * (const Z& a,const Z& b){34 Z c;35 for(int i = 0;i < 2 ; ++ i)36 for(int j = 0;j < 2;j++){37 c.m[i][j] = 0;38 for(int k = 0;k < 2;k++)39 c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j]) % mod;40 }41 return c;42 }43 Z mpow(int n){44 Z ret , p;45 ret = B, p = A;46 while(n){47 if(n&1) ret = ret * p;48 p = p * p;49 n >>= 1;50 }51 return ret;52 }53 int main(){54 LL n,m,flag = 0;;55 while(cin>>n>>m){56 if(m == 0){57 LL x = 4 * Pow(3,n-1) % mod;58 cout << x << endl;59 continue;60 }61 for(int i = 1;i <= m;i++)62 cin>>s[i].a>>s[i].b;63 64 if(m == 1){65 LL x = Pow(3,n-1);66 cout << x << endl;67 continue;68 }69 sort(s+1,s+m+1,cmp);70 LL x = 1;71 Z ant;72 s[0].a = 0;73 for(int i = 1;i <= m; ++ i){74 75 if(s[i-1].a != 0){76 LL abs = s[i].a - s[i-1].a - 2;77 if(abs < 0)78 {79 if(s[i-1].b[0] == s[i].b[0]) {x = 0;break;}80 continue;81 }82 ant = mpow(abs);83 if(s[i-1].b[0] == s[i].b[0])84 x = x * (ant.m[0][0]*3 + ant.m[1][0]*3)%mod;85 else x = x * (ant.m[0][0]*2 + ant.m[1][0]*3)%mod;86 87 }88 else {89 x = x * Pow(3,s[i].a - 1) % mod;90 }91 if(i == m && s[i].a < n){92 x = x * Pow(3,n-s[i].a) % mod;93 }94 }95 cout << (x%mod + mod)%mod<< endl;96 }97 }
zoj - 3538（矩阵乘法）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。