题面：
思路：
一眼看上去是三个递推......好像还挺麻烦的
仔细观察一下，发现也就是一个线性递推，但是其中后面的常数项比较麻烦
观察一下，这里面有以下三个递推是比较麻烦的
第一个是$k^2$到$left(k+1 ight)^2$，这一步可以把$left(k+1 ight)^2$展开，变成$k^2+2k+1$
第二、三个是$w$和$z$的递推，这个就直接在转移矩阵里面乘以一个自己就好了
所以我们可以构建这样的状态矩阵：
$egin{bmatrix}albrack i brack&albrack i+1 brack&blbrack i brack&blbrack i+1 brack&cleft[i ight]&cleft[i+1 ight]&k^2&k&w&z&1end{bmatrix}$
转移矩阵见代码
最后快速幂就解决了
Code：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define mx 1e16 6 #define ll long long 7 using namespace std; 8 inline ll read(){ 9 ll re=0,flag=1;char ch=getchar(); 10 while(ch>'9'||ch<'0'){ 11 if(ch=='-') flag=-1; 12 ch=getchar(); 13 } 14 while(ch>='0'&&ch<='9') re=(re<<1)+(re<<3)+ch-'0',ch=getchar(); 15 return re*flag; 16 } 17 ll n,MOD; 18 inline ll pmul(ll l,ll r){ 19 ll re=0;if(l<r) swap(l,r); 20 while(r){ 21 if(r&1){ 22 re+=l; 23 if(re>mx) re%=MOD; 24 } 25 r>>=1;l=l+l;if(l>mx) l%=MOD; 26 } 27 return re%MOD; 28 } 29 struct ma{ 30 ll a[20][20],n,m; 31 ma(){memset(a,0,sizeof(a));n=m=0;} 32 void clear(){memset(a,0,sizeof(a));n=m=0;} 33 const ma operator *(const ma &b){ 34 ma re;re.n=n;re.m=b.m;ll i,j,k; 35 for(i=1;i<=n;i++){ 36 for(j=1;j<=b.m;j++){ 37 for(k=1;k<=m;k++){ 38 re.a[i][j]+=pmul(a[i][k],b.a[k][j]); 39 re.a[i][j]%=MOD; 40 } 41 } 42 } 43 return re; 44 } 45 const void operator =(const ma &b){ 46 n=b.n;m=b.m;ll i,j; 47 for(i=1;i<=n;i++) for(j=1;j<=m;j++) a[i][j]=b.a[i][j]; 48 } 49 }A,B,ans; 50 //A={a[k],a[k+1],b[k],b[k+1],c[k],c[k+1],k^2,k,w^k,z^k,1} 51 /* 52 matrix B 53 0 q 0 0 0 0 0 0 0 0 0 54 1 p 0 1 0 1 0 0 0 0 0 55 0 0 0 u 0 0 0 0 0 0 0 56 0 1 1 v 0 1 0 0 0 0 0 57 0 0 0 0 0 x 0 0 0 0 0 58 0 1 0 1 1 y 0 0 0 0 0 59 0 r 0 0 0 0 1 0 0 0 0 60 0 t 0 0 0 1 2 1 0 0 0 61 0 0 0 1 0 0 0 0 w 0 0 62 0 0 0 0 0 1 0 0 0 z 0 63 0 1 0 0 0 2 1 1 0 0 1 64 */ 65 ma ppow(ma x,ma y,ll t){ 66 while(t){ 67 if(t&1) x=x*y; 68 y=y*y;t>>=1; 69 } 70 return x; 71 } 72 int main(){ 73 n=read();MOD=read(); 74 ll p=read(),q=read(),r=read(),t=read(),u=read(),v=read(),w=read(),x=read(),y=read(),z=read(); 75 A.n=1;A.m=11; 76 A.a[1][1]=1;A.a[1][2]=3;A.a[1][3]=1;A.a[1][4]=3;A.a[1][5]=1;A.a[1][6]=3; 77 A.a[1][7]=A.a[1][8]=A.a[1][11]=1;A.a[1][9]=w;A.a[1][10]=z; 78 B.n=B.m=11; 79 B.a[2][1]=1;B.a[4][3]=1;B.a[6][5]=1;B.a[11][11]=1; 80 B.a[2][2]=p;B.a[1][2]=q;B.a[4][2]=1;B.a[6][2]=1;B.a[7][2]=r;B.a[8][2]=t;B.a[11][2]=1; 81 B.a[4][4]=u;B.a[3][4]=v;B.a[2][4]=1;B.a[6][4]=1;B.a[9][4]=1; 82 B.a[6][6]=x;B.a[5][6]=y;B.a[2][6]=1;B.a[4][6]=1;B.a[10][6]=1;B.a[8][6]=1;B.a[11][6]=2; 83 B.a[7][7]=1;B.a[8][7]=2;B.a[11][7]=1; 84 B.a[8][8]=1;B.a[11][8]=1; 85 B.a[9][9]=w;B.a[10][10]=z; 86 ans=ppow(A,B,n-1); 87 printf("nodgd %lld Ciocio %lld Nicole %lld ",ans.a[1][1],ans.a[1][3],ans.a[1][5]); 88 }