[luogu1707] 刷题比赛 [矩阵快速幂]

题面：

传送门

思路：

一眼看上去是三个递推......好像还挺麻烦的

仔细观察一下，发现也就是一个线性递推，但是其中后面的常数项比较麻烦

观察一下，这里面有以下三个递推是比较麻烦的

第一个是$k^2$到$\left(k+1\right)^2$，这一步可以把$\left(k+1\right)^2$展开，变成$k^2+2k+1$

第二、三个是$w$和$z$的递推，这个就直接在转移矩阵里面乘以一个自己就好了

所以我们可以构建这样的状态矩阵：

$\begin{bmatrix}a\lbrack i\rbrack&a\lbrack i+1\rbrack&b\lbrack i\rbrack&b\lbrack i+1\rbrack&c\left[i\right]&c\left[i+1\right]&k^2&k&w&z&1\end{bmatrix}$

转移矩阵见代码

最后快速幂就解决了

Code：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define mx 1e16

 #define ll long long

 using namespace std;

 inline ll read(){

     ll re=,flag=;char ch=getchar();

     while(ch>''||ch<''){

         if(ch=='-') flag=-;

         ch=getchar();

     }

     while(ch>=''&&ch<='') re=(re<<)+(re<<)+ch-'',ch=getchar();

     return re*flag;

 }

 ll n,MOD;

 inline ll pmul(ll l,ll r){

     ll re=;if(l<r) swap(l,r);

     while(r){

         if(r&){

             re+=l;

             if(re>mx) re%=MOD;

         }

         r>>=;l=l+l;if(l>mx) l%=MOD;

     }

     return re%MOD;

 }

 struct ma{

     ll a[][],n,m;

     ma(){memset(a,,sizeof(a));n=m=;}

     void clear(){memset(a,,sizeof(a));n=m=;}

     const ma operator *(const ma &b){

         ma re;re.n=n;re.m=b.m;ll i,j,k;

         for(i=;i<=n;i++){

             for(j=;j<=b.m;j++){

                 for(k=;k<=m;k++){

                     re.a[i][j]+=pmul(a[i][k],b.a[k][j]);

                     re.a[i][j]%=MOD;

                 }

             }

         }

         return re;

     }

     const void operator =(const ma &b){

         n=b.n;m=b.m;ll i,j;

         for(i=;i<=n;i++) for(j=;j<=m;j++) a[i][j]=b.a[i][j];

     }

 }A,B,ans;

 //A={a[k],a[k+1],b[k],b[k+1],c[k],c[k+1],k^2,k,w^k,z^k,1}

 /*

 matrix B

 0 q 0 0 0 0 0 0 0 0 0

 1 p 0 1 0 1 0 0 0 0 0

 0 0 0 u 0 0 0 0 0 0 0

 0 1 1 v 0 1 0 0 0 0 0

 0 0 0 0 0 x 0 0 0 0 0

 0 1 0 1 1 y 0 0 0 0 0

 0 r 0 0 0 0 1 0 0 0 0

 0 t 0 0 0 1 2 1 0 0 0

 0 0 0 1 0 0 0 0 w 0 0

 0 0 0 0 0 1 0 0 0 z 0

 0 1 0 0 0 2 1 1 0 0 1

 */

 ma ppow(ma x,ma y,ll t){

     while(t){

         if(t&) x=x*y;

         y=y*y;t>>=;

     }

     return x;

 }

 int main(){

     n=read();MOD=read();

     ll p=read(),q=read(),r=read(),t=read(),u=read(),v=read(),w=read(),x=read(),y=read(),z=read();

     A.n=;A.m=;

     A.a[][]=;A.a[][]=;A.a[][]=;A.a[][]=;A.a[][]=;A.a[][]=;

     A.a[][]=A.a[][]=A.a[][]=;A.a[][]=w;A.a[][]=z;

     B.n=B.m=;

     B.a[][]=;B.a[][]=;B.a[][]=;B.a[][]=;

     B.a[][]=p;B.a[][]=q;B.a[][]=;B.a[][]=;B.a[][]=r;B.a[][]=t;B.a[][]=;

     B.a[][]=u;B.a[][]=v;B.a[][]=;B.a[][]=;B.a[][]=;

     B.a[][]=x;B.a[][]=y;B.a[][]=;B.a[][]=;B.a[][]=;B.a[][]=;B.a[][]=;

     B.a[][]=;B.a[][]=;B.a[][]=;

     B.a[][]=;B.a[][]=;

     B.a[][]=w;B.a[][]=z;

     ans=ppow(A,B,n-);

     printf("nodgd %lld\nCiocio %lld\nNicole %lld\n",ans.a[][],ans.a[][],ans.a[][]);

 }

巴特西

[luogu1707] 刷题比赛 [矩阵快速幂]

最新文章

热门文章