Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- using namespace std;
- ifstream f("pepeuri.in");
- ofstream g("pepeuri.out");
- long long n , m , k , i , j , a[10] , p[10][10] , b[10][10] ,c[10][10] , sol , suma , cif[31],u ,t ,d ;
- void ridiclapatrat()
- {
- for(i=0;i<=9;i++)
- for(j=0;j<=9;j++)
- {
- c[i][j]=0;
- for(k=0;k<=9;k++)c[i][j]=(c[i][j]+p[i][k]*p[k][j])%m;
- }
- for(i=0;i<=9;i++)
- for(j=0;j<=9;j++)p[i][j]=c[i][j];
- }
- void inmultesc()
- {
- for(i=0;i<=9;i++)
- for(j=0;j<=9;j++)
- {
- c[i][j]=0;
- for(k=0;k<=9;k++)c[i][j]=(c[i][j]+p[i][k]*b[k][j])%m;
- }
- for(i=0;i<=9;i++)
- for(j=0;j<=9;j++)p[i][j]=c[i][j];
- }
- int main()
- {
- f >> n;
- m=10111121 ;
- t=n-2;
- d=0 ;
- while( t!=0 )
- {
- d++;
- cif[d]=t%2;
- t=t/2;
- }
- a[0]=3;a[1]=2;a[2]=2;a[3]=2;a[4]=1;a[5]=1;a[6]=1;a[7]=2;a[8]=2;a[9]=1;
- for(i=0;i<=9;i++)p[i][i]=1;
- b[0][0]=1;
- b[0][1]=1;
- b[1][0]=1;
- for(i=0;i<=4;i++)b[i][4-i]=1;
- for(i=0;i<=9;i++)b[i][9-i]=1;
- b[7][9]=1;
- b[8][8]=1;
- b[9][7]=1;
- for(u=d;u>=1;u--)
- {
- if(cif[u]==1){ridiclapatrat();inmultesc();}
- else {ridiclapatrat();}
- }
- sol=0;
- for(i=0;i<=9;i++)
- {
- suma=0;
- for(j=0;j<=9;j++)suma=(suma+p[i][j]*a[j])%m;
- sol=(sol+suma)%m;
- }
- g << sol ;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement