首页 > 代码库 > poj 3734
poj 3734
题意:有N个空格,我们可以涂上红,蓝,绿,黄,要求红和绿为偶数个,问多少种方案
思路:我们假设当前有a种红绿为偶数方案,b种绿红一种为偶数的方案,c种绿红为奇数的方案,那么下一个位置
ai+1=2*ai+bi;
bi+1=2*bi+2*ai+2*ci
ci+1=2*ci+bi
所以矩阵快速幂搞一搞
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <algorithm> 6 #include <cmath> 7 typedef long long ll; 8 using namespace std; 9 const long long mod = 10007; 10 struct prog 11 { 12 long long a[8][8]; 13 }; 14 prog s,B; 15 prog matrixmul(prog a,prog b) 16 { 17 prog c; 18 for(int i=1;i<4;++i)for(int j=1;j<8;++j) 19 { 20 c.a[i][j]=0; 21 for(int k=1;k<4;k++) 22 c.a[i][j]+=(a.a[i][k]*b.a[k][j])%mod; 23 c.a[i][j]%=mod; 24 } 25 return c; 26 } 27 prog mul(prog s,int k) 28 { 29 prog ans; 30 for(int i=1;i<4;++i)for(int j=1;j<4;++j) ans.a[i][j]=(i==j)?1:0; 31 while(k){ 32 if(k&1) 33 ans=matrixmul(ans,s); 34 k>>=1; 35 s=matrixmul(s,s); 36 } 37 return ans; 38 } 39 int main() 40 { 41 int t; 42 scanf("%d",&t); 43 while(t--){ 44 ll n; 45 scanf("%I64d",&n); 46 n--; 47 B.a[1][1]=2; B.a[1][2]=2; B.a[1][3]=0; 48 B.a[2][1]=1; B.a[2][2]=2; B.a[2][3]=1; 49 B.a[3][1]=0; B.a[3][2]=2; B.a[3][3]=2; 50 s=mul(B,n); 51 printf("%d\n",((2*s.a[1][1]+2*s.a[2][1])%mod+mod)%mod); 52 } 53 return 0; 54 }
poj 3734
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。