HDU 5793

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 <iostream>
 2 #include <cstdio>
 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
",ans);
30     }
31 }

我自倾杯，君且随意