hdu 4602 Partition（快速幂）

 1 #include<stdio.h>
 2 
 3 const int mod=1e9+7;
 4 
 5 #define LL __int64
 6 
 7 LL p[2][2];
 8 LL q[1][2];
 9 
10 LL bb(LL a,LL b,LL c,LL d)
11 {
12     return (a*c%mod+b*d%mod)%mod;
13 }
14 
15 LL aa(int n)
16 {
17     LL a,b,c,d;
18     LL x,y;
19     p[0][0]=2;
20     p[0][1]=0;
21     p[1][0]=1;
22     p[1][1]=2;
23 
24     q[0][0]=2;
25     q[0][1]=1;
26     while(n)
27     {
28         a=p[0][0];b=p[0][1];c=p[1][0];d=p[1][1];
29         x=q[0][0];y=q[0][1];
30         if(n&1){
31             q[0][0]=bb(x,y,a,c);
32             q[0][1]=bb(x,y,b,d);
33         }
34         p[0][0]=bb(a,b,a,c);
35         p[0][1]=bb(a,b,b,d);
36         p[1][0]=bb(c,d,a,c);
37         p[1][1]=bb(c,d,b,d);
38 
39         n>>=1;
40     }
41     return (q[0][0]%mod);
42 }
43 
44 int main()
45 {
46     int T,n,m;
47     scanf("%d",&T);
48 
49     while(T--)
50     {
51         scanf("%d%d",&n,&m);
52         if(n<m)
53             printf("0
");
54         else if(n-m==0)
55             printf("1
");
56         else if(n-m==1)
57             printf("2
");
58         else 
59             printf("%I64d
",aa(n-m-1));
60     }
61     return 0;
62 }