首页 > 代码库 > CodeForces 185A 快速幂

CodeForces 185A 快速幂

技术分享

  一开始找矩阵快速幂的题来做时就看到了这题,题意就是让你求出如图所示的第n个三角形中指向向上的小三角形个数。从图中已经很容易看出递推关系了,我们以f[n]表示第n个大三角形中upward的小三角形个数,g[n]表示第n个大三角形中downward的小三角形个数,然后,递推关系就是:

  f[n]= 3*f[n-1]+1*g[n-1];

  g[n]= 3*g[n-1]+1*f[n-1];

其中f[0]=1,g[0]=0(一开始的纯三角形是从n=0开始的),然后……就没有然后了,直觉上感觉f[n]很难表示成只含有f[i]的式子,一时没想到该如何再和矩阵联系起来了(实际上两个不同的变量还是能构造出矩阵出来的:[ f(n), g(n) ]T= [ [3,1], [1,3] ]* [ f(n-1), g(n-1) ]T 即可,该矩阵就是 [ [3,1], [1,3] ]T,在这里写矩阵毕竟很不方便,自己在草稿纸上写出来看看吧,更直观),当时一时脑子发热没往这个方向去想,于是便转向了第二个思路。

  我再次观察了图发现它的确很有规律,无论是f[n]还是g[n]都是 1+2+3+……+k 的和嘛,k就是大三角形的层数,而层数也很有规律,第n个三角形的层数是前一个的两倍(也不难看出,因为每个子三角形每次都划分为两层),所以k= 2n,所以f[n]= (1+2n)*2n-1,g[n]也很容易表示出来,不过此时已经不需要g[n]了,之后,便是一个简简单单的裸快速幂即可!

 1 #include<cstdio> 2 typedef long long LL; 3 const LL mod= 1000000007; 4  5 LL quick_mod(LL a, LL b, LL m){ 6     LL ans= 1; 7     a%= m; 8     while(b){ 9         if(b&1)      ans= ans*a%m;10         a= a*a%m;11         b>>=1;12     }13     return ans;14 }15 16 int main(){17     LL n;18     scanf("%I64d",&n);19     if(!n)    puts("1");20     else    printf("%I64d\n",(1+quick_mod(2,n,mod))*quick_mod(2,n-1,mod)%mod);21     return 0;22 }

  后来我把输入改成 while(~scanf(....)) 来试了下,也过了,可以看出cf上是单组数据读入的,即便这样用while也行,注意添加好文件结束符EOF即可。

  水过后,我看着1000000007这个数值觉得用long long来处理好像也是有点浪费了,相乘是会溢出,但相加绝对不会溢出,只是已经很接近 int的上限而已。于是,我装了下B,把快速幂中的相乘改为了相加(同样利用快速幂的原理,二进制处理连续的加),这样,就能避开了long long(虽说节省不了什么资源,但可以训练下处理数据溢出的一些能力。不过在比赛中还是绝对不要这样给自己找麻烦,保险才是最重要的),写好快速乘取模后,却忘了在最后的 (1+2n)*2n-1 这里还有一个乘法,所以也调试了一点点时间。

 1 #include<cstdio> 2 typedef long long LL; 3 const int mod= 1000000007; 4  5 int quick_mul(int a, int b, int m){ 6     int ans= 0; 7     a%= m; 8     while(b){ 9         if(b&1)      ans= (ans+a)%m;10         a= (a+a)%m;11         b>>=1;12     }13     return ans;14 }15 16 int quick_mod(int a, LL b, int m){17     int ans= 1;18     a%= m;19     while(b){20         if(b&1)      ans= quick_mul(ans,a,m);21         a= quick_mul(a,a,m);22         b>>=1;23     }24     return ans;25 }26 27 int main(){28     LL n;29     while(~scanf("%I64d",&n)){30         if(!n)    puts("1");31         else {32             int tmp1= quick_mod(2,n-1,mod);33             int tmp2= tmp1*2%mod;34             printf("%d\n",quick_mul((1+tmp2),tmp1,mod));35         }36     }37     return 0;38 }

  至此,装逼完成,成功水过。

CodeForces 185A 快速幂