本文共 1435 字，大约阅读时间需要 4 分钟。
矩阵快速幂。先要处理出第i列每个状态下，让该状态填满，下一列可以出现的状态。因为N较大，可以矩阵加速。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-8;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}inline int read(){ char c = getchar(); while(!isdigit(c)) c = getchar(); int x = 0; while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } return x;}LL n,MOD;struct Matrix{ long long A[18][18]; int R, C; Matrix operator*(Matrix b);};Matrix X, Y, Z;Matrix Matrix::operator*(Matrix b){ Matrix c; memset(c.A, 0, sizeof(c.A)); int i, j, k; for (i = 1; i <= R; i++) for (j = 1; j <= b.C; j++) for (k = 1; k <= C; k++) c.A[i][j] = (c.A[i][j] + (A[i][k] * b.A[k][j]) % MOD) % MOD; c.R = R; c.C = b.C; return c;}void dfs(int a,int b,int t,int c){ if(t==4) { X.A[c+1][b+1]=1; return; } if(a&(1< > 1; X = X*X; } Z = Z*Y; printf("%lld\n",Z.A[1][16]);}int main(){ while(~scanf("%lld%lld",&n,&MOD)) { if(n==0&&MOD==0) break; n++; init(); work(); } return 0;}
转载于:https://www.cnblogs.com/zufezzt/p/5740777.html