http://poj.org/problem?id=3420
简单版：http://poj.org/problem?id=2663（题解：https://blog.csdn.net/weixin_43272781/article/details/88983956）
题意：在4*N的方格内塞满规格是1*2的砖头，横放竖放都可以，问一共有多少种放法。
C++版本一
/*
*@Author: STZG
*@Language: C++
*/
//#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int s[25][25];
int b[25][25];
int a[25][25];
char str;
struct node{};
void dfs(int x,int now,int pre) {
if (x==4) {++s[pre][now];return;}
dfs(x+1,now<<1|1,pre<<1);
dfs(x+1,now<<1,pre<<1|1);
if (x<3) dfs(x+2,now<<2,pre<<2);
}
void Matrix(int a[25][25],int b[25][25]){
int c[25][25];
memset(c,0,sizeof(c));
for(int i=0;i<16;i++){
for(int j=0;j<16;j++){
for(int k=0;k<16;k++){
c[i][j]=(c[i][j]+a[i][k]*b[k][j])%m;
}
}
}
for(int i=0;i<16;i++){
for(int j=0;j<16;j++){
a[i][j]=c[i][j];
}
}
}
int power(int k){
for(int i=0;i<16;i++){
for(int j=0;j<16;j++){
a[i][j]=(i==j);
b[i][j]=s[i][j];
}
}
while(k){
if(k&1)Matrix(a,b);
Matrix(b,b);
k>>=1;
}
return a[0][0];
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//
dfs(0,0,0);
while(~scanf("%d%d",&n,&m)&&n+m){
cout<<power(n)<<endl;
}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
题解：
递推式：a[i]=a[i-1]+5*a[i-2]+a[i-3]-a[i-4];
由于N高达10^9，所以要用矩阵进行优化。
|0 1 0 0|
|0 0 1 0|
|0 0 0 1|
|-1 1 5 1|
与
|a[i-3]|
|a[i-2]|
|a[i-1]|
|a[i]|
相乘
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <cstdlib>
#include <algorithm>
#define LL long long
using namespace std;
const int Max = 10;
int Mod;
struct Matrix
{
int n,m;
int a[Max][Max];
void clear()//清空矩阵
{
n=0;
m=0;
memset(a,0,sizeof(a));
}
Matrix operator * (const Matrix &b)const//矩阵相乘
{
Matrix tmp;
tmp.clear();
tmp.n=n;
tmp.m=b.m;
for(int i=0;i<n;i++)
{
for(int j=0;j<b.m;j++)
{
for(int k=0;k<m;k++)
{
tmp.a[i][j]=(tmp.a[i][j]+(a[i][k]%Mod)*(b.a[k][j]%Mod))%Mod;
}
}
}
return tmp;
}
};
void Pow(int m)
{
Matrix s;
s.clear();
s.n=4;
s.m=4;
s.a[3][3]=1;s.a[3][2]=5;
s.a[3][1]=1;s.a[3][0]=-1;
s.a[1][2]=1;s.a[2][3]=1;
s.a[0][1]=1;
Matrix ans;
ans.clear();
ans.n=4;
ans.m=1;
ans.a[0][0]=1;
ans.a[1][0]=5;
ans.a[2][0]=11;
ans.a[3][0]=36;
while(m)//快速幂
{
if(m&1)
{
ans=s*ans;
}
s=s*s;
m>>=1;
}
printf("%d\n",ans.a[3][0]);
}
int main()
{
int n;
while(scanf("%d %d",&n,&Mod),n)
{
if(n<4)
{
switch(n)
{
case 1:
printf("%d\n",1%Mod);
break;
case 2:
printf("%d\n",5%Mod);
break;
case 3:
printf("%d\n",11%Mod);
break;
}
continue;
}
Pow(n-4);
}
return 0;
} C++版本三
题解：构造矩阵 DFS 矩阵快速幂
数据很大，不能直接搞了，我们矩乘一下。0表示已放置，1表示未放置。dfs跑出一个16∗16的转移矩阵，然后矩乘，最后输出ans[0][0]就可以了。
参考文章：原博客
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define HAS 4001
#define inf 2147483640
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;
int n,m;
LL a[16][16],tmp[16][16],t[16][16],ans[16][16];
void dfs(int x,int now,int pre) {
if (x==4) {++a[pre][now];return;}
dfs(x+1,now<<1|1,pre<<1);
dfs(x+1,now<<1,pre<<1|1);
if (x<3) dfs(x+2,now<<2,pre<<2);
}
void power() {
for (int i=0;i<16;i++) {
for (int j=0;j<16;j++) t[i][j]=a[i][j],ans[i][j]=0;
ans[i][i]=1;
}
while (n) {
if (n&1) {
for (int i=0;i<16;i++)
for (int j=0;j<16;j++) {
tmp[i][j]=0;
for (int k=0;k<16;k++) (tmp[i][j]+=ans[i][k]*t[k][j]%m)%=m;
}
for (int i=0;i<16;i++)
for (int j=0;j<16;j++) ans[i][j]=tmp[i][j];
}
n>>=1;
for (int i=0;i<16;i++)
for (int j=0;j<16;j++) {
tmp[i][j]=0;
for (int k=0;k<16;k++) (tmp[i][j]+=t[i][k]*t[k][j]%m)%=m;
}
for (int i=0;i<16;i++)
for (int j=0;j<16;j++) t[i][j]=tmp[i][j];
}
}
int main() {
dfs(0,0,0);
while (scanf("%d%d",&n,&m)!=EOF && n && m) {
power();
printf("%lld\n",ans[0][0]);
}
return 0;
} C++版本四
题解：
设f(n,state)：第n列铺砖状态为state时的情况数，状态state可以是：(0代表还未铺砖，1代表已被砖占据):
state 0:0
0
0
0
state 1:1
1
0
0
或者
0
0
1
1
state 2:
1
0
0
1
state 3:
0
1
1
0
state 4:
1
1
1
1
需要用到的情况就这么多，为什么呢，举个例子
先写出四行三列的格子，其中定义状态：
0 1 2 3 ... 14 15
X00 XX0 X00 XX0 X00 XX0
X00 X00 XX0 XX0 XX0 XX0
X00 X00 X00 X00 XX0 XX0
X00 X00 X00 X00 XX0 XX0
为考虑第2列的所有状态，其中x代表已被填满，0代表还是空的
再定义：
0 1 2 3 ... 14 15
XX0 XXX XX0 XXX XX0 XXX
XX0 XX0 XXX XXX XXX XXX
XX0 XX0 XX0 XX0 XXX XXX
XX0 XX0 XX0 XX0 XXX XXX
为考虑第三列的所有状态
那么第三列中状态0可以由第2列中的哪些状态转化而来呢？显然第2列的状态0，3，9，12，15可以通过铺砖得到第三列的状态0；
而计算状态0转移过程所需要用到的状态0，3，9，12，15可以由那些状态转移得到呢？除了状态9需要用到前一列的状态0和6得到，其他状态都可以互推，不需要新的状态。
那么需要用到的状态就是一开始所说的那几种，并且转移方程可以写成如下递推式：
f(n+1, 0) = f(n, 0) + 2 * f(n, 1) + f(n, 2) + f(n, 4)
f(n+1, 1) = f(n, 0) + f(n, 1)
f(n+1, 2) = f(n, 0) + f(n, 3)
f(n+1, 3) = f(n, 2)
f(n+1, 4) = f(n, 0)
写成矩阵的形式：(f(n+1,0),f(n+1,1),f(n+1,2),f(n+1,3),f(n+1,4))=A*(f(n,0),f(n,1),f(n,2),f(n,3),f(n,4));
A=1 1 1 0 1
2 1 0 0 0
1 0 0 1 0
0 0 1 0 0
1 0 0 0 0
B=A^N,B[0][0]即是第N列砖的铺砖的所有可能数。
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#include<queue>
using namespace std;
typedef vector<int> vec;
typedef vector<vec> mat;
typedef long long ll;
const int M_MAX = 100000;
mat A, B;
ll n;
int N, M;
mat mul(mat &A,mat &B,int &M) {
mat C(A.size(),vec(B[0].size()));
for (int i = 0; i < A.size();i++) {
for (int k = 0; k < B.size();k++) {
for (int j = 0; j < B[0].size();j++) {
C[i][j] = (C[i][j]+A[i][k]*B[k][j]) % M;
}
}
}
return C;
}
mat pow(mat A,ll n){
mat B(A.size(),vec(A[0].size()));
for (int i = 0; i < A.size();i++) {
B[i][i] = 1;
}
while (n>0) {
if (n & 1)B = mul(B, A,M);
A = mul(A, A,M);
n >>= 1;
}
return B;
}
int main() {
while (scanf("%d%d",&N,&M)!=EOF&&N) {
mat A(5,vec(5));
A[0][0] =A[0][1]=A[0][2]=A[0][4]=1;
A[1][0] = 2; A[1][1] = 1;
A[2][0] = A[2][3] = 1;
A[3][2] = 1;
A[4][0] = 1;
A = pow(A, N);
printf("%d\n",A[0][0]);
}
return 0;
}
京公网安备 11010502036488号