洛谷 1707 刷题比赛

/*
矩阵稍微有点难搞 不过也是可以推出来
注意防爆...
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
ll n,mod,p,q,r,t,u,v,w,x,y,z;
ll f[12][12],a[12][12];
ll slow_mul(ll a,ll b)
{
    ll ans=0;
    while(b)
      {
          if(b&1)
            {
                b--;ans+=a;ans%=mod;
          }
        a<<=1;a%=mod;b>>=1;
      }
    return ans;
}
void mul(ll a[12][12],ll b[12][12])
{
    ll c[12][12];memset(c,0,sizeof(c));
    for(int i=1;i<=11;i++)
      for(int j=1;j<=11;j++)
        for(int k=1;k<=11;k++)
          c[i][j]=(c[i][j]+slow_mul(a[i][k],b[k][j]))%mod;
    for(int i=1;i<=11;i++)
      for(int j=1;j<=11;j++)
        a[i][j]=c[i][j];
}
int main()
{
    cin>>n>>mod>>p>>q>>r>>t>>u>>v>>w>>x>>y>>z;n-=2;
    f[1][1]=f[1][3]=f[1][5]=3;f[1][2]=f[1][4]=f[1][6]=1;
    f[1][7]=f[1][8]=f[1][9]=1;f[1][10]=w;f[1][11]=z;
    a[1][1]=p;a[2][1]=q;a[7][1]=r;a[8][1]=t;a[3][3]=u;
    a[4][3]=v;a[5][5]=x;a[6][5]=y;a[9][5]=a[8][7]=2;
    a[10][10]=w;a[11][11]=z;
    a[1][2]=a[1][3]=a[1][5]=a[3][1]=a[3][4]=a[3][5]=1;
    a[5][1]=a[5][3]=a[7][7]=a[8][5]=a[8][8]=a[9][1]=1;
    a[9][7]=a[9][8]=a[9][9]=a[10][3]=a[11][5]=a[5][6]=1;
    while(n)
      {
          if(n&1)mul(f,a);
          mul(a,a);n>>=1;
      }
    cout<<"nodgd"<<" "<<f[1][1]<<endl;
    cout<<"Ciocio"<<" "<<f[1][3]<<endl;
    cout<<"Nicole"<<" "<<f[1][5]<<endl;
    return 0;
}