时间限制：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[][];
} mx;
int pow[];
int n, m, mod, len;
Mat operator * (Mat a, Mat b) {
Mat c;
memset (c.mat, , sizeof c.mat);
for (int k = ; k < ( << m); k++)
for (int i = ; i < ( << m); i++)
for (int j = ; j < ( << m); j++)
(c.mat[i][j] += (a.mat[i][k] * b.mat[k][j]) % mod) %= mod;
return c; }
inline int div2() {
int ans[] = {};
int i, res = ;
for(i = ; i < len; ++i) {
ans[i] = (pow[i]+res*)/;
res = (pow[i]+res*)%;
}
if(ans[] == ) len--;
for(i = +(ans[] == ); i < len+(ans[] == ); i++)
pow[i-(ans[] == )] = ans[i];
return res;
}
Mat operator ^ (Mat a, int pow[]) {
Mat c;
for (int i = ; i < ( << m); i++)
for (int j = ; j < ( << 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 ();
while(cin >> s >> m >> mod){
for (int i = ; i < s.size(); ++i)
pow[i] = s[i] - '';
len = s.size();
for (int i = len - ; i >= ; i--) {
if (pow[i]) {
--pow[i];
break;
}
else
pow[i] = ;
}
if (pow[] == ) {
for (int i = ; i < len - ; i++) pow[i] = ;
pow[--len]=;
}
for (int i = ; i < ( << m); i++)
for (int j = ; j < ( << m); j++) {
mx.mat[i][j] = ;
for (int k = , tem = i ^ j; k < m - ; k++)
if ( (tem & << k) == && (tem & << k + ) ==
&&( ( (i & << k) > && (i & << k + ) > ) || ( ( (i & << k) == && (i & << k + ) == ) ) ) ) {
mx.mat[i][j] = ;
break;
}
}
mx = mx ^ pow;
int ans = ;
for (int i = ; i < ( << m); i++)
for (int j = ; j < ( << m); j++) {
ans += mx.mat[i][j];
while (ans >= mod) ans -= mod;
}
cout << ans << endl;
}
}