首页 > 代码库 > SGU 197.Nice Patterns Strike Back
SGU 197.Nice Patterns Strike Back
时间限制：0.5s
空间限制：6M
题意：
给出长n（n<=10^100）和宽m（m<=5）的地面,铺上黑色和白色的地板,使得没有任意一个2*2大小的地面铺同种颜色的方案数是多少.
Solution:
状态压缩,一个数字的对应为01分别代表铺白色和黑色地板,对于每一列有(1<<m)种状态.
我们可以构造一个矩阵,mat[i][j]代表,第一列是状态是i,第二列是j的方案数,显然mat[i][j]不是0就是1,而且很容易判断构造.
然后我们只要对这个矩阵进行快速幂运算,幂为(n-1),当然不要忘记取模,最后把mat所有元素加起来就是我们想要的答案了.
由于n比较大,所以要做大数的减一,和除以二的运算.
code
#include <iostream>#include <cstring>#include <string>using namespace std;struct Mat { int mat[100][100];} mx;int pow[109];int n, m, mod, len;Mat operator * (Mat a, Mat b) { Mat c; memset (c.mat, 0, sizeof c.mat); for (int k = 0; k < (1 << m); k++) for (int i = 0; i < (1 << m); i++) for (int j = 0; j < (1 << m); j++) (c.mat[i][j] += (a.mat[i][k] * b.mat[k][j]) % mod) %= mod; return c;}inline int div2() { int ans[103] = {0}; int i, res = 0; for(i = 0; i < len; ++i) { ans[i] = (pow[i]+res*10)/2; res = (pow[i]+res*10)%2; } if(ans[0] == 0) len--; for(i = 0+(ans[0] == 0); i < len+(ans[0] == 0); i++) pow[i-(ans[0] == 0)] = ans[i]; return res;}Mat operator ^ (Mat a, int pow[]) { Mat c; for (int i = 0; i < (1 << m); i++) for (int j = 0; j < (1 << m); j++) c.mat[i][j] = (i == j); while (len) { if (div2() ) c = c * a; a = a * a; } return c;}string s;int main() { ios::sync_with_stdio (0); while(cin >> s >> m >> mod){ for (int i = 0; i < s.size(); ++i) pow[i] = s[i] - ‘0‘; len = s.size(); for (int i = len - 1; i >= 0; i--) { if (pow[i]) { --pow[i]; break; } else pow[i] = 9; } if (pow[0] == 0) { for (int i = 0; i < len - 1; i++) pow[i] = 9; pow[--len]=0; } for (int i = 0; i < (1 << m); i++) for (int j = 0; j < (1 << m); j++) { mx.mat[i][j] = 1; for (int k = 0, tem = i ^ j; k < m - 1; k++) if ( (tem & 1 << k) == 0 && (tem & 1 << k + 1) == 0&&( ( (i & 1 << k) > 0 && (i & 1 << k + 1) > 0) || ( ( (i & 1 << k) == 0 && (i & 1 << k + 1) == 0) ) ) ) { mx.mat[i][j] = 0; break; } } mx = mx ^ pow; int ans = 0; for (int i = 0; i < (1 << m); i++) for (int j = 0; j < (1 << m); j++) { ans += mx.mat[i][j]; while (ans >= mod) ans -= mod; } cout << ans << endl; }}
SGU 197.Nice Patterns Strike Back
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。