本文共 3637 字，大约阅读时间需要 12 分钟。
题意：给你两种颜色，黑色和白色，填充n*m的方格，每个格子一种颜色，但要保证在每个2*2的方格内不能出现同一中颜色
题解：枚举当前行和上一行的所有合法状态，矩阵快速幂
假如：2 * 2的方格，合法状态为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#include #include #include #include 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)//大数除法{ 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%mod int 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)//大数减法{ 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){//枚举当前行，与上一行的合法状态 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; } }}
转载地址：http://gdsgi.baihongyu.com/