首页 > 代码库 > hdu 1005 简单题

hdu 1005 简单题

2024-07-27 21:04:01   218人阅读

　　　今早水出的第一道题，带着情绪做的，竟然1Y了，确实惊奇。这道简单的线性递推取模，直接递推是不行的，因为n的规模达到了100,000,000，要么超时要么超内存。可以用矩阵快速幂来搞，根据题意构建出对应的矩阵后即可（第一次写的，用结构体来进行矩阵相乘运算），代码如下：

 1 #include<cstdio> 2  3 struct matrix{ 4     int a,b,c,d; 5     matrix(int _a=1, int _b=0, int _c=1, int _d=0) { 6         a=_a;    b=_b;    c=_c;    d=_d; 7     } 8     matrix operator *(const matrix &m2){ 9         return matrix((a*m2.a%7+b*m2.c%7)%7, (a*m2.b%7+b*m2.d%7)%7, (c*m2.a%7+d*m2.c%7)%7, (c*m2.b%7+d*m2.d%7)%7);10     }11     matrix square(){12         return matrix((a*a%7+b*c%7)%7, b*(a+d)%7, c*(a+d)%7, (b*c%7+d*d%7)%7);13     }14 };15 16 int calcu(matrix m, int p)17 {18     matrix ans(1,0,0,1);19     while(p){20         if(p&1)    ans= ans*m;21         m= m.square();22         p>>=1;23     }24     return (ans.a+ans.c)%7;25 }26 27 int main()28 {29     int a,b,n;30     while(scanf("%d%d%d",&a,&b,&n),a){31         if(n<=2)    puts("1");32         else    printf("%d\n", calcu(matrix(a,1,b,0),n-2));33     }34     return 0;35 }

　　实际上，这道题还有更优的做法，就是找循环周期，因为f[n]只与前两个有关，而且是模7，所以它的循环周期是7*7-1=48（为何这样算我也不知如何证明，留待以后再想），下面也附上AC代码：

 1 #include<cstdio> 2 int f[49]= {0,1,1}; 3  4 int main() 5 { 6     int a,b,n,i; 7     while(scanf("%d%d%d",&a,&b,&n), a){ 8         for(i=3; i<=48; ++i) 9             f[i]= (a*f[i-1]+b*f[i-2])%7;10         f[0]= f[48];11         printf("%d\n",f[n%48]);12     }13     return 0;14 }

 

hdu 1005 简单题


联系
我们