fork download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #define Clear(A) memset(A,0,sizeof(A))
  4.  
  5. int Mod,S;
  6.  
  7. struct Mat{
  8.     unsigned int d[32][32];
  9.     Mat operator * (const Mat &oth) const{
  10.         Mat ret;
  11.         Clear(ret.d);
  12.         int i,j,k;
  13.         for (i=0;i<S;i++)
  14.           for (j=0;j<S;j++)
  15.             for (k=0;k<S;k++)
  16.               ret.d[i][j]+=d[i][k]*oth.d[k][j];
  17.         for (i=0;i<S;i++)
  18.           for (j=0;j<S;j++)
  19.             ret.d[i][j]%=Mod;
  20.         return ret;
  21.     }
  22. }Stard,A,B,C;
  23. int m;
  24. char str[205];
  25.  
  26. void dfs(int ps,int depth,int ns){
  27.     if (depth>=m){
  28.         Stard.d[ps][ns]=1;
  29.         return;
  30.     }
  31.     if ( depth==0 || ( (ns&(1<<depth-1)) != (ps&(1<<depth-1)) )
  32.     || ( (bool)(ps&(1<<depth-1)) != (bool)(ps&(1<<depth)) ) ){
  33.         dfs(ps,depth+1,ns);
  34.         dfs(ps,depth+1,ns|(1<<depth));
  35.     }
  36.     else
  37.         dfs(ps,depth+1,(ns|(1<<depth))^(ps&(1<<depth)));
  38. }
  39.  
  40. void init(){
  41.     int i;
  42.     scanf("%s %d %d",str,&m,&Mod);
  43.     if (strlen(str)==1 && str[0]=='1') { printf("%d\n",(1<<m)%Mod); return; }
  44.     for (i=0;i<1<<m;i++)
  45.       dfs(i,0,0);
  46.     S=1<<m;
  47. }
  48.  
  49. int L;
  50. int Num[105];
  51. bool n[405];
  52.  
  53. void div(){
  54.     int i,tmp=0;
  55.     for (i=L;i>=1;i--){
  56.         tmp=tmp*10+Num[i];
  57.         Num[i]=tmp/2;
  58.         tmp%=2;
  59.     }
  60.     while (L>=1 && Num[L]==0) L--;
  61. }
  62.  
  63. void dec(){
  64.     int i;
  65.     Num[1]--;
  66.     for (i=1;Num[i]<0;i++){
  67.         Num[i]+=10;
  68.         Num[i+1]--;
  69.     }
  70.     while (L>=1 && Num[L]==0) L--;
  71. }
  72.  
  73. void solve(){
  74.     memset(n,0,sizeof(n));
  75.     int i,cnt=0;
  76.     L=strlen(str);
  77.     for (i=L-1;i>=0;i--) Num[++cnt]=str[i]-'0';
  78.     cnt=0;
  79.     dec();
  80.     while (L>0){
  81.         n[++cnt]=Num[1]&1;
  82.         div();
  83.     }
  84.     L=cnt;
  85.     for (i=0;i<1<<m;i++) A.d[0][i]=1;
  86.     C=Stard;
  87.     for (i=L-1;i>=1;i--){
  88.         C=C*C;
  89.         if (n[i]) C=C*Stard;
  90.     }
  91.     A=A*C;
  92.     int ret=0;
  93.     for (i=0;i<S;i++) ret+=A.d[0][i];
  94.     ret%=Mod;
  95.     printf("%d\n",ret);
  96. }
  97.  
  98. int main(){
  99.     int Tc;
  100.     scanf("%d",&Tc);
  101.     for (int i=1;i<=Tc;i++){
  102.         Clear(Stard.d);
  103.         Clear(A.d);
  104.         Clear(C.d);
  105.         init();
  106.         if (!(strlen(str)==1 && str[0]=='1')) solve();
  107.         if (i!=Tc) puts("");
  108.     }
  109.     return 0;
  110. }
stdin
copy 
Standard input is empty
compilation info 
prog.cpp: In function ‘void dfs(int, int, int)’:
prog.cpp:31: warning: suggest parentheses around + or - inside shift
prog.cpp:31: warning: suggest parentheses around + or - inside shift
prog.cpp:32: warning: suggest parentheses around + or - inside shift
prog.cpp: In function ‘void init()’:
prog.cpp:42: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
prog.cpp: In function ‘int main()’:
prog.cpp:100: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
stdout
copy 
Standard output is empty
https://ideone.com/l0UAc
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!