历史性的时刻！！！
推了一晚上！和hyc一起萌萌哒地推出来了！！
被摧残蹂躏的智商啊！！！
然而炒鸡高兴！！
（请不要介意蒟蒻的内心独白。。）
设a[i]为扫到第i行时的方案数。
易知，对于一行1*4的格子，只有一种方案把它铺满。
首先，对于当前的第i行，如果它不和第i-1行有联系（也就是它是独立的一行），那么就有1*a[i-1]=a[i-1]种方案。
如果第i行和第i-1行有联系（2行间互相联系），那么共有一下四种方案：
如果第i行、第i-1行、第i-2行都有联系（3行间两两联系），那么共有两种方案（此图以及的轴对称图形）：
如果第i行、第i-1行、第i-2行、第i-3行都有联系（4行间两两联系），那么共有三种方案（上面两种方案加下面一种）：
……
一直递推下去，我们可以发现：
2行间相互联系 --> 4种方案
3行间相互联系 --> 2种方案
4行间相互联系 --> 3种方案
……
奇数行相互联系（n>2) --> 2种方案
偶数行相互联系（n>2) --> 3种方案
所以，我们可以得出：
a[i]=a[i-1]+4*a[i-2]+2*(a[i-3]+a[i-5]+……+a[(i&1)?0:1])+3*(a[i-4]+a[i-6]+……+a[(i&1)?1:0]);
设s=a[i-3]+a[i-5]+……+a[(i&1)?0:1]，t=a[i-4]+a[i-6]+……+a[(i&1)?1:0];
该递推式可以转化为矩阵乘法：
代码如下：
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> using namespace std; const int N=1000000010; int Mod; struct node{ int s[5][5]; int sx,sy; }; node mult(node a,node b) { node t; t.sx=a.sx;t.sy=b.sy; memset(t.s,0,sizeof(t.s)); for(int i=1;i<=a.sx;i++) for(int j=1;j<=b.sy;j++) for(int k=1;k<=a.sx;k++) { t.s[i][j]+=(a.s[i][k]*b.s[k][j])%Mod; t.s[i][j]%=Mod; } return t; } void quickpow(int n) { if(n==0) {printf("0 ");return ;} node a; a.s[1][1]=1%Mod,a.s[1][2]=4%Mod,a.s[1][3]=2%Mod,a.s[1][4]=3%Mod; a.s[2][1]=1%Mod,a.s[2][2]=0%Mod,a.s[2][3]=0%Mod,a.s[2][4]=0%Mod; a.s[3][1]=0%Mod,a.s[3][2]=1%Mod,a.s[3][3]=0%Mod,a.s[3][4]=1%Mod; a.s[4][1]=0%Mod,a.s[4][2]=0%Mod,a.s[4][3]=1%Mod,a.s[4][4]=0%Mod; a.sx=4;a.sy=4; node b; b.s[1][1]=b.s[2][2]=b.s[3][3]=b.s[4][4]=1%Mod; b.s[1][2]=b.s[1][3]=b.s[1][4]=0%Mod; b.s[2][1]=b.s[2][3]=b.s[2][4]=0%Mod; b.s[3][1]=b.s[3][2]=b.s[3][4]=0%Mod; b.s[4][1]=b.s[4][2]=b.s[4][3]=0%Mod; b.sx=4;b.sy=4; while(n) { if(n&1) b = mult(a,b); a = mult(a,a); n>>=1; } node c; c.sx=4;c.sy=1; c.s[1][1]=1%Mod;c.s[2][1]=c.s[3][1]=c.s[4][1]=0%Mod; c = mult(b,c); printf("%d ",c.s[1][1]); return ; } int main() { while(1) { int x; scanf("%d%d",&x,&Mod); if(x==0) return 0; quickpow(x); } return 0; }