手动列出前5项 可发现规律

1 /* 2 推导公式 3 a[n] = 2^(n-1) + (n-2)*2^(n-3) 4 */ 5 #include
      
        6 #include
       
         7 #include
        
          8 using namespace std; 9 typedef long long int64;10 const int64 mod = 1e9+7;11 12 int64 FastPow( int64 n,int64 m ){
    //n^m13     int64 sum = 1;14     while( m>=1 ){15         if( m%2==1 ){16             sum *= n;17             sum %= mod;18         }19         n *= n;20         n %= mod;21         m/=2;22     }23     return sum;24 }25 26 int main(){27     int T;28     scanf("%d",&T);29     while( T-- ){30         int64 n,k;31         //scanf("%lld%lld",&n,&k);32         scanf("%I64d%I64d",&n,&k);33         if( k>n ){34             printf("0\n");35             continue;36         }37         if( k==n ){38             printf("1\n");39             continue;40         }41         int64 delta = k-1;42         int64 Index = n-delta;43         44         if( Index==1 ){45             printf("1\n");46             continue;47         }48         if( Index==2 ){49             printf("2\n");50             continue;51         }52         53         //printf("%lld\n",(FastPow2(2,Index-1)%mod+FastPow2(2,Index-3)*(Index-2)%mod)%mod);54         printf("%I64d\n",(FastPow(2,Index-1)%mod+FastPow(2,Index-3)*(Index-2)%mod)%mod);55     }56     return 0;57 }