题目链接：
分析：
洛谷的一道原创题，对于练习矩阵加速递推非常不错。
首先我们看一下递推式：
\(a[k+2]=p*a[k+1]+q*a[k]+b[k+1]+c[k+1]+r*k^2+t*k+1;\)
\(b[k+2]=u*b[k+1]+v*b[k]+a[k+1]+c[k+1]+w^k;\)\(c[k+2]=x*c[k+1]+y*c[k]+a[k+1]+b[k+1]+z^k+k+2;\)有点吓人，我想在做这道题的人都能对类似\(p*a[k+1]\)都能进行转移矩阵的构建，主要我们处理后面这些。
设\(f[k]=k^2\)
则\(f[k+1]=(k+1)^2=f[k]+2*k+1;\)
设\(g[k]=k\)
则\(g[k+1]=g[k]+1;\)
设\(h[k]=w^k\)
则\(h[k+1]=h[k]*w;\)
设\(p[k]=z^k\)
则\(p[k+1]=p[k]*z;\)
设\(q[k]=x*k\)
则\(q[k+1]=q[k]+x;\)
然后就全都转化成线性递推，搞一个状态矩阵：
\(ans={a2,a1,b2,b1,c2,c1,f[k],g[k],h[k],p[k],k,1}\)
转移矩阵：
\({p,q,1,0,1,0,r,0,0,0,t,1}\)
\({1,0,0,0,0,0,0,0,0,0,0,0}\)
\({1,0,u,v,1,0,0,0,1,0,0,0}\)
\({0,0,1,0,0,0,0,0,0,0,0,0}\)
\({1,0,1,0,x,y,0,0,0,1,1,2}\)
\({0,0,0,0,1,0,0,0,0,0,0,0}\)
\({0,0,0,0,0,0,1,0,0,0,2,1}\)
\({0,0,0,0,0,0,0,1,0,0,0,1}\)
\({0,0,0,0,0,0,0,0,w,0,0,0}\)
\({0,0,0,0,0,0,0,0,0,z,0,0}\)
\({0,0,0,0,0,0,0,0,0,0,1,1}\)
\({0,0,0,0,0,0,0,0,0,0,0,1}\)
好了，你就可以开始了。
然而有个很毒瘤的地方：你可能需要快速乘
然后一开始我不知道在这里卡了好久
我只想说
### 这题对于一个蒟蒻而言太毒瘤了！！！
代码：
#include#include #include #include #include #include #define ll long long using namespace std;const int maxn=17;ll N,k;int p,q,r,t,u,v,w,x,y,z;ll q_mul(ll a,ll b){ ll ans=0; while(b) { if(b&1) ans=(ans+a)%k; a=(a+a)%k; b>>=1; } return ans;}struct Matrix{ int n,m; ll ma[maxn][maxn]; Matrix(int _n){n=m=_n;memset(ma,0,sizeof(ma));for(register int i=1;i<=n;i++)ma[i][i]=1;} Matrix(int _n,int _m){n=_n,m=_m;memset(ma,0,sizeof(ma));} Matrix(){;} Matrix operator *(const Matrix &b)const{ Matrix ans=Matrix(n,b.m); for(register int i=1;i<=n;i++){ for(register int j=1;j<=b.m;j++){ ll tmp=0; for(register int o=1;o<=m;o++){ tmp+=q_mul(ma[i][o],b.ma[o][j]);//(ma[i][o]%k*b.ma[o][j]%k)%k; //if(tmp>1000000)tmp=tmp%k; } ans.ma[i][j]=tmp%k; } } return ans; } Matrix operator ^(const ll& C)const { ll c=C; Matrix res=*this; Matrix ans=Matrix(n); while(c){ if(c&1)ans=ans*res; res=res*res; c=c>>1; } return ans; } };void print(ll x)//输出{ if(x<0) { x =-x; putchar('-'); } if(x>9) print(x/10); putchar(x%10+'0');}int main(){ scanf("%lld %lld %d %d %d %d %d %d %d %d %d %d",&N,&k,&p,&q,&r,&t,&u,&v,&w,&x,&y,&z); Matrix ans=Matrix(12,1); ans.ma[1][1]=3,ans.ma[2][1]=1,ans.ma[3][1]=3,ans.ma[4][1]=1,ans.ma[5][1]=3,ans.ma[6][1]=1; ans.ma[7][1]=1,ans.ma[8][1]=1,ans.ma[9][1]=w,ans.ma[10][1]=z,ans.ma[11][1]=1,ans.ma[12][1]=1; Matrix A=Matrix(12,12); A.ma[1][1]=p,A.ma[1][2]=q,A.ma[1][3]=1,A.ma[1][5]=1,A.ma[1][7]=r,A.ma[1][11]=t,A.ma[1][12]=1; A.ma[2][1]=1; A.ma[3][1]=1,A.ma[3][3]=u,A.ma[3][4]=v,A.ma[3][5]=1,A.ma[3][9]=1; A.ma[4][3]=1; A.ma[5][1]=1,A.ma[5][3]=1,A.ma[5][5]=x,A.ma[5][6]=y,A.ma[5][10]=1,A.ma[5][11]=1,A.ma[5][12]=2; A.ma[6][5]=1; A.ma[7][7]=1,A.ma[7][11]=2,A.ma[7][12]=1; A.ma[8][8]=A.ma[8][12]=1; A.ma[9][9]=w,A.ma[10][10]=z,A.ma[11][11]=A.ma[11][12]=1,A.ma[12][12]=1; A=A^(N-2); ans=A*ans; printf("nodgd %lld\nCiocio %lld\nNicole %lld",ans.ma[1][1],ans.ma[3][1],ans.ma[5][1]); return 0;}