首页 > 代码库 > HDU----(4291)A Short problem(快速矩阵幂)

HDU----(4291)A Short problem(快速矩阵幂)

2024-07-23 20:00:55   225人阅读

A Short problem

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1716    Accepted Submission(s): 631


Problem Description
　　According to a research, VIM users tend to have shorter fingers, compared with Emacs users.
　　Hence they prefer problems short, too. Here is a short one:
　　Given n (1 <= n <= 1018), You should solve for
g(g(g(n))) mod 109 + 7

　　where
g(n) = 3g(n - 1) + g(n - 2)

g(1) = 1

g(0) = 0
 

 

Input
　　There are several test cases. For each test case there is an integer n in a single line.
　　Please process until EOF (End Of File).
 

 

Output
　　For each test case, please print a single line with a integer, the corresponding answer to this case.
 

 

Sample Input
012
 

 

Sample Output
0142837
 

 

Source
2012 ACM/ICPC Asia Regional Chengdu Online
 
此题出得比较精妙，
分析:假设g(g(g(n)))=g(x),x可能超出范围,但是由于mod 10^9+7,所以可以求出x的循环节

求出x的循环节后,假设g(g(g(n)))=g(x)=g(g(y)),即x=g(y),y也可能非常大,但是由x的循环节可以求出y的循环节

如何求循环节点：

 1 /*采用事先处理自己可以求出来*/ 2 LL work(LL mod){   3   LL a=0,b=1; 4     for(LL i=2;;++i) 5     {     6       a=(b*3+a)%mod; 7         a=a^b; 8         b=a^b; 9         a=a^b;10         if(a == 0 && b == 1)  return i;11  }

所以依次将mod1带入得到mod2=222222224;

然后将mod2带入得到mod3=183120;

然后就是快速矩阵了。

代码：

 1 //#define LOCAL 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #define LL __int64 6 using namespace std; 7 const int mod1 =1000000007; 8 const int mod2=222222224; 9 const int mod3=183120;10 11 LL mat[2][2];12 LL ans[2][2];13 LL n;14 15 void Matrix(LL a[][2],LL b[][2],LL mod)16 {17     LL cc[2][2]={0};18     for(int i=0;i<2;i++)19     {20       for(int j=0;j<2;j++)21       {22           for(int k=0;k<2;k++)23         {24             cc[i][j]=(cc[i][j]+a[i][k]*b[k][j])%mod;25         }26       }27     }28     for(int i=0;i<2;i++)29     {30       for(int j=0;j<2;j++)31       {32           a[i][j]=cc[i][j];33       }34     }35 }36 37 void pow(LL w,LL mod)38 {39   while(w>0)40   {41     if(w&1) Matrix(ans,mat,mod);42      w>>=1;43      if(w==0)break;44      Matrix(mat,mat,mod);45   }46 }47 void input(LL w,LL mod)48 {49      mat[0][0]=3;50      mat[0][1]=mat[1][0]=1;51      mat[1][1]=0;52      ans[0][0]=ans[1][1]=1;53      ans[0][1]=ans[1][0]=0;54      pow(w,mod);55 //     printf("%I64d\n",ans[0][0]);56 }57 void work(int i,__int64 w)58 {59   if(i==4||w==0||w==1)60   {61       if(w==0)62          printf("0\n");63       else if(w==1)64           printf("1\n");65       else66       printf("%I64d\n",ans[0][0]);67       return ;68   }69   LL mod;70   if(i==1)mod=mod3;71   else if(i==2)mod=mod2;72   else if(i==3)mod=mod1;73   input(w-1,mod);74   work(i+1,ans[0][0]);75 }76 int main()77 {78   #ifdef LOCAL79    freopen("test.in","r",stdin);80   #endif81   while(scanf("%I64d",&n)!=EOF)82      work(1,n);83  return 0;84 }
View Code

 

HDU----(4291)A Short problem(快速矩阵幂)


联系
我们