vijosP1194 Domino
【思路】
矩阵相乘。
参考Matrix67的文章:
【代码】
#include<cstdio>
#include<cstring>
#include<iostream>
#define FOR(a,b,c) for(int a=(b);a<(c);a++)
using namespace std; const int maxn = ;
const int ag[]={,,,,,,,};
typedef long long LL; int n,m,MOD; struct Matrix{
int r,c;
LL N[maxn][maxn];
void init(int r,int c) {
this->r=r, this->c=c;
memset(N,,sizeof(N));
}
Matrix operator*(Matrix& B)const{
Matrix A=*this,C;
C.init(A.r,B.c);
for(int i=;i<C.r;i++)
for(int j=;j<C.c;j++)
for(int k=;k<A.c;k++)
C.N[i][j] = (C.N[i][j]+A.N[i][k]*B.N[k][j])%MOD;
return C;
}
Matrix pow(int p) {
Matrix tmp=*this;
Matrix ans;
ans.init(r,r);
for(int i=;i<r;i++) ans.N[i][i]=;
while(p) {
if(p&) ans=ans*tmp;
tmp=tmp*tmp;
p>>=;
}
return ans;
}
};
int main() {
scanf("%d%d%d",&n,&m,&MOD);
Matrix ans;
int all=<<m;
ans.init(all,all);
for(int i=;i<all;i++)
for(int j=;j<all;j++)
if( ((~i)&j) == ((~i)&(all-))) {
int l=;
for(int r=;r<=;r++) l=l||((i&j)==ag[r]);
ans.N[i][j]=l;
}
ans=ans.pow(n);
printf("%d",ans.N[all-][all-]);
return ;
}