http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2317? ? ?

題意：給你兩種顏色，黑色和白色，填充n*m的方格，每個格子一種顏色，但要保證在每個2*2的方格內(nèi)不能出現(xiàn)同一中顏色

題解：枚舉當(dāng)前行和上一行的所有合法狀態(tài)，矩陣快速冪

? 假如：2 * 2的方格，合法狀態(tài)為1

? ? ? ? ? ?{0 1 1 1}
?{1 1 1 1}

sum+= ?{1,1,1,1}? *?{1 1 1 1} ??

?{1 1 1 0}

可以想想。。。。。。。

/* * this code is made by fenger * Problem: 1214 * Verdict: Accepted * Submission Date: 2014-10-19 16:46:55 * Time: 212MS * Memory: 1864KB */ #include<cstdio> #include<cmath> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int m; int p[35][35]; int cnt,mod; struct Z{int m[33][33];Z(){memset(m,0,sizeof(m));}void init(){for(int i = 0;i < cnt;i++)m[i][i] = 1;} }; string solve(string a)//大數(shù)除法 {string s;int l = a.size();int c = 1,num = 0,ans = a[0] - '0';if(ans >= 2) {c = 0;ans = 0;s="";}for(int i = c;i < l;i++){ans = ans*10 + a[i] - '0';s += ans / 2 + '0';ans %= 2;}if(s == "") s = "0";return s; } int Pow(int a,string x){//2^x%modint res = 1;while(x[0] != '0'){if((x[x.size()-1] -'0')&1) res = res * a % mod;a = a * a % mod;x = solve(x);}return res; } Z operator * (Z a , Z b){//矩陣乘法Z c;for(int i = 0;i < cnt;i++)for(int k = 0;k < cnt;k++)if(a.m[i][k])for(int j = 0;j < cnt;j++)c.m[i][j] = (c.m[i][j] + a.m[i][k]*b.m[k][j]) % mod;return c; } Z Pow1(string x,Z a){//矩陣快速冪Z ret;ret.init();while(x[0]!='0'){if((x[x.size()-1] - '0')&1) ret = ret * a;a = a * a;x = solve(x);}return ret; } string mul(string a)//大數(shù)減法 {int l = a.size();if(a[l-1] - '0' >= 1){a[l-1] -= 1;return a;}else{string s = "";a[l-1] += 9;for(int i = l - 2;i >= 0;i--)if(a[i] == '0') a[i] = '9';else {a[i] -= 1;break;}if(a[0] == '0'){for(int i = 1;i < l;i++) s += a[i];return s;}else {return a;}} } void dfs(int cur , int now ,int pre){//枚舉當(dāng)前行，與上一行的合法狀態(tài)if(cur > m) return;if(cur == m){p[pre][now] = 1;return ;}if(cur == 0){dfs(cur+1,(now<<1)|1,(pre<<1)|1);dfs(cur+1,(now<<1)|1,(pre<<1));dfs(cur+1,(now<<1),(pre<<1));dfs(cur+1,(now<<1),(pre<<1)|1);}else{int k1 = now&1,k2 = pre&1;if(k1 == k2 && k1){dfs(cur+1,(now<<1)|1,(pre<<1));dfs(cur+1,(now<<1),(pre<<1)|1);dfs(cur+1,(now<<1),(pre<<1));}else if(k1 == k2&&(!k1)){dfs(cur+1,(now<<1),(pre<<1)|1);dfs(cur+1,(now<<1)|1,(pre<<1));dfs(cur+1,(now<<1)|1,(pre<<1)|1);}else if(k1 != k2){dfs(cur+1,(now<<1)|1,(pre<<1)|1);dfs(cur+1,(now<<1)|1,(pre<<1));dfs(cur+1,(now<<1),(pre<<1));dfs(cur+1,(now<<1),(pre<<1)|1);}} } int main(){string str;while(cin >> str >> m >> mod){int l = str.size();if(m == 1){int w = Pow(2,str);cout << w << endl;}else if(l == 1 && str[0] == '1'){int w = pow(2,m);cout << (w%mod) << endl;}else{cnt = (1 << m);memset(p,0,sizeof(p));dfs(0,0,0);Z s;for(int i = 0;i < cnt;i++)for(int j = 0;j < cnt;j++)s.m[i][j] = p[i][j];str = mul(str);s = Pow1(str,s);int ans = 0;for(int i = 0;i < cnt;i++)for(int j = 0;j < cnt;j++)ans = (ans + s.m[i][j])%mod;cout << ans << endl;}} }

總結(jié)

以上是生活随笔為你收集整理的ZOJ 2317Nice Patterns Strike Back（矩阵快速幂）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。