网站开发新闻管理系统的背景,编程培训班在线培训,网站公司网站开发方案,做网站腾讯云服务器Quad Tiling
poj 3420
题目大意
在一个4n的棋盘上#xff0c;用12的多米诺骨牌把他填满#xff0c;问有多少种方法
输入样例
1 10000
3 10000
5 10000
0 0 输出样例
1
11
95数据范围 1⩽N⩽1091 \leqslant N \leqslant 10^91⩽N⩽109 0M⩽1050 M \leqslant 10…Quad Tiling
poj 3420
题目大意
在一个4×n的棋盘上用1×2的多米诺骨牌把他填满问有多少种方法
输入样例
1 10000
3 10000
5 10000
0 0 输出样例
1
11
95数据范围
1⩽N⩽1091 \leqslant N \leqslant 10^91⩽N⩽109 0M⩽1050 M \leqslant 10^50M⩽105
解题思路
对于放多米诺骨牌可以用状压DP 但直接状压会TLE 考虑矩阵乘法 可以先把状态之间的关系预处理出来 然后快速幂即可
代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define wyc mod
using namespace std;
ll n, mod;
struct matrix
{ll n, m, a[20][20];matrix operator *(const matrix b) const{matrix c;c.n n;c.m b.m;for (int i 1; i c.n; i)for (int j 1; j c.m; j)c.a[i][j] 0;for (int i 1; i c.n; i)for (int k 1; k m; k)for (int j 1; j c.m; j)c.a[i][j] (c.a[i][j] a[i][k] * b.a[k][j] % wyc) % wyc;return c;}
}A, B;
ll ggg(ll x, ll y, ll z, ll g)
{return x (y1) (z2) (g3) 1;
}
void pp(ll x, ll y, ll z, ll g)
{ll xx x^1, yy y^1, zz z^1, gg g^1;B.a[ggg(xx, yy, zz, gg)][ggg(x, y, z, g)] 1;if (!xx !yy){B.a[ggg(1, 1, zz, gg)][ggg(x, y, z, g)] 1;if (!zz !gg)B.a[ggg(1, 1, 1, 1)][ggg(x, y, z, g)] 1;}if (!yy !zz)B.a[ggg(xx, 1, 1, gg)][ggg(x, y, z, g)] 1;if (!zz !gg)B.a[ggg(xx, yy, 1, 1)][ggg(x, y, z, g)] 1;return;
}
void Counting(ll x)
{while(x){if (x1) A A * B;B B * B;x1; }return;
}
int main()
{while(1){scanf(%lld%lld, n, mod);if (!n) break;for (int i 1; i 16; i){A.a[1][i] 0;for (int j 1; j 16; j)B.a[i][j] 0;}A.n 1;A.m B.n B.m 16;A.a[1][1] 1;//初始状态A.a[1][4] 1;A.a[1][7] 1;A.a[1][13] 1;A.a[1][16] 1;for (int i 0; i 1; i)for (int j 0; j 1; j)for (int k 0; k 1; k)for (int c 0; c 1; c)pp(i, j, k, c);//预处理矩阵Counting(n - 1);//快速幂printf(%lld\n, A.a[1][16] % wyc);}return 0;
}
