矩阵快速幂

``` # include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> using namespace std; //读题后，我认为此题为快速幂,但是%数太小 //猜测正解矩阵快速幂 typedef long long ll; int n,m,p; const int q=1e9+7; const int maxn=1e6+10; int a[maxn],b[maxn],c[maxn]; int f[11000]; inline int sub(int x,int y){ x=x-y;if(x<0)x+=p;return x; } struct matrix{ int a[105][105],n,m;//矩阵的长宽及矩阵中的元素 inline void init(int n1,int m1){//初始化矩阵 n=n1,m=m1; memset(a,0,sizeof(a)); } friend matrix operator * (matrix a,matrix b) {//重载运算符 * matrix c;c.init(a.n,b.m);//每次相邻的长宽将失去 for(int i=0;i<=c.n;i++) for(int j=0;j<c.m;j++) for(int k=0;k<a.m;k++){//更新矩阵 c.a[i][j] += 1ll * a.a[i][k] * b.a[k][j] %q; c.a[i][j]%=q; } return c; } friend matrix operator ^ (matrix a,int b){ matrix ret;ret.init(a.n,a.m); for(int i=0;i<a.n;i++)ret.a[i][i]=1; while(b){ if(b&1)ret=ret*a; a=a*a; b>>=1; } return ret; } }A,T; int main() { scanf("%d%d%d",&n,&m,&p); for(int i=1;i<=n;i++){scanf("%d",&a[i]);a[i]%=p;} for(int i=1;i<=n;i++){scanf("%d",&b[i]);b[i]%=p;} for(int i=1;i<=n;i++){scanf("%d",&c[i]);c[i]%=p;} T.init(p,p); for(int j=0;j<p;j++) for(int i=1;i<=n;i++) T.a[j][sub(j,b[i])]++; A.init(p,1); for(int i=1;i<=n;i++)A.a[a[i]][0]++; T = T ^ (m-2); A = T * A; for(int i=0;i<p;i++)f[i]=A.a[i][0]; int ans=0; for(int i=1;i<=n;i++) { int t=b[i]+c[i]; t%=p; t = -t; if(t<0)t+=p; ans+=f[t]; ans%=q; } printf("%d",ans); } ```