HDU 5793 - A Boring Question

题意：

　　计算 ( ∑(0≤K₁,K₂...K_m≤n )∏(1≤j<m) C[K_j, K_j+1]  ) % 1000000007=? (C[Kj, Kj+1] 为组合数)

    

分析:

　　利用二项式展开： (a + b) ^ n =  ∑(r = 0, n) (C[n, r] * a^(n-r) * b^r )

    

    化简：

           ∑(0≤K₁,K₂...K_m≤n )∏(1≤j<m) C[K_j, K_j+1]

    

         = ∑( K_m = 0, n ) ∑( K_m-1 = 0, Km ) ∑( K_m-2 = 0, K_m-1 )...∑( K₁ = 0, K₂ ) ( C[K_m, K_m-1] * C[K_m-1, K_m-2] *...*C[K₂, K₁]  )

           

         = ∑( K_m = 0, n ) ∑( K_m-1 = 0, Km )C[K_m, K_m-1]  ∑( K_m-2 = 0, K_m-1 )C[K_m-1, K_m-2] ... ∑( K₂ = 0, K₃ )C[K₃, K₂]  ∑( K₁ = 0, K₂)C[K₂, K₁]   //后面的积可分别提到和式前面

                                                                                                                                    

         = ∑( K_m = 0, n ) ∑( K_m-1 = 0, Km )C[K_m, K_m-1]  ∑( K_m-2 = 0, K_m-1 )C[K_m-1, K_m-2] ... ∑( K₂ = 0, K₃ ) ( C[K₃, K₂] * 2^K₂ )  

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 // ∑( K₁ = 0, K₂)C[K₂, K₁]  为(1 + 1) ^ k₂ 的二项式展开

                                                                                                                                    

         = ∑( K_m = 0, n ) m ^ K_m          //∑( K₂ = 0, K₃ ) ( C[K₃, K₂] * 2^K₂ ) 为 (1 + 2) ^ k₃ 的二项式展开 ，接下来依次向上化简

         

         = ( m^(n+1) - 1 ) / ( m - 1 ) 　　//等比数列求和公式

         

    接下来求快速幂和逆元即可.

　　（博客园怎么连个公式编辑器都没有= =）

1 #include 
     
       2 #include 
      
        3 using namespace std; 4 #define LL long long 5 const LL MOD = 1000000007; 6 LL PowMod(LL a, LL p, LL MOD) 7 { 8     int res = 1; 9     while(p)10     {11         if(p&1) res = (res * a) %MOD;12         p >>= 1;13         a = (a * a) % MOD;14     }15     return res;16 }17 int t;18 LL n,m;19 int main()20 {21     scanf("%d",&t);22     while(t--)23     {24         scanf("%lld%lld", &n, &m);25         LL ans = PowMod(m, n+1, MOD);26         --ans;27         LL inv = PowMod(m-1, MOD-2, MOD);28         ans = (ans * inv) % MOD;29         printf("%lld\n",ans);30     }31 }