2 条题解
-
0
#include<bits/stdc++.h> using namespace std; typedef long long LL; const LL P=2009; struct node { LL a[101][101]; node(){memset(a,0,sizeof a);} }; int n,t; node operator*(node A,node B) { node C; for (int i=1;i<=n*9;i++) for (int j=1;j<=n*9;j++) for (int k=1;k<=n*9;k++) C.a[i][j]=(C.a[i][j]+ A.a[i][k]*B.a[k][j])%P; return C; } node qpow(node A,int b) { node C;for(int i=1;i<=n*9;i++)C.a[i][i]=1; for(;b;b>>=1) { if(b&1)C=C*A; A=A*A; } return C; } int main() { scanf("%d%d",&n,&t); node f; for(int i=1;i<=n;i++) for(int j=1;j<=8;j++) f.a[i+j*n][i+(j-1)*n]=1; for(int i=1;i<=n;i++) { for(int j=1, x;j<=n;j++) { scanf("%1d", &x); if(x)f.a[i][j+(x-1)*n]=1; } } f=qpow(f,t); printf ("%d\n", f.a[1][n]); return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 17:03:24
#include<bits/stdc++.h> using namespace std; typedef long long LL; const LL P=2009; struct node { LL a[101][101]; node(){memset(a,0,sizeof a);} }; int n,t; node operator*(node A,node B) { node C; for (int i=1;i<=n*9;i++) for (int j=1;j<=n*9;j++) for (int k=1;k<=n*9;k++) C.a[i][j]=(C.a[i][j]+ A.a[i][k]*B.a[k][j])%P; return C; } node qpow(node A,int b) { node C;for(int i=1;i<=n*9;i++)C.a[i][i]=1; for(;b;b>>=1) { if(b&1)C=C*A; A=A*A; } return C; } int main() { scanf("%d%d",&n,&t); node f; for(int i=1;i<=n;i++) for(int j=1;j<=8;j++) f.a[i+j*n][i+(j-1)*n]=1; for(int i=1;i<=n;i++) { for(int j=1,x;j<=n;j++) { scanf("%1d",&x); if(x)f.a[i][j+(x-1)*n]=1; } } f=qpow(f,t); printf ("%d\n", f.a[1][n]); return 0; }
- 1
