HDU 5793A Boring Question 多校训练

There are an equation. 
∑0≤k1,k2,⋯km≤n∏1⩽j<m(kj+1kj)%1000000007=?∑0≤k1,k2,⋯km≤n∏1⩽j<m(kj+1kj)%1000000007=? 
We define that (kj+1kj)=kj+1!kj!(kj+1−kj)!(kj+1kj)=kj+1!kj!(kj+1−kj)! . And (kj+1kj)=0(kj+1kj)=0 while kj+1<kjkj+1<kj. 
You have to get the answer for each nn and mm that given to you. 
For example,if n=1n=1,m=3m=3, 
When k1=0,k2=0,k3=0,(k2k1)(k3k2)=1k1=0,k2=0,k3=0,(k2k1)(k3k2)=1; 
Whenk1=0,k2=1,k3=0,(k2k1)(k3k2)=0k1=0,k2=1,k3=0,(k2k1)(k3k2)=0; 
Whenk1=1,k2=0,k3=0,(k2k1)(k3k2)=0k1=1,k2=0,k3=0,(k2k1)(k3k2)=0; 
Whenk1=1,k2=1,k3=0,(k2k1)(k3k2)=0k1=1,k2=1,k3=0,(k2k1)(k3k2)=0; 
Whenk1=0,k2=0,k3=1,(k2k1)(k3k2)=1k1=0,k2=0,k3=1,(k2k1)(k3k2)=1; 
Whenk1=0,k2=1,k3=1,(k2k1)(k3k2)=1k1=0,k2=1,k3=1,(k2k1)(k3k2)=1; 
Whenk1=1,k2=0,k3=1,(k2k1)(k3k2)=0k1=1,k2=0,k3=1,(k2k1)(k3k2)=0; 
Whenk1=1,k2=1,k3=1,(k2k1)(k3k2)=1k1=1,k2=1,k3=1,(k2k1)(k3k2)=1. 
So the answer is 4.

InputThe first line of the input contains the only integer TT,(1≤T≤10000)(1≤T≤10000) 
Then TT lines follow,the i-th line contains two integers nn,mm,(0≤n≤109,2≤m≤109)(0≤n≤109,2≤m≤109) 
OutputFor each nn and mm,output the answer in a single line.Sample Input

2

1 2

2 3

Sample Output

3

13

根据题意可以推出公式 
∑0≤k1,k2,⋯km≤n∏1⩽j<m(kj+1kj)%1000000007= m^0 + m^1 + m^2 + ... + m^n = ( pow(m,n+1) - 1 / m - 1 ) % mod;
注意这个题目中是除法后取余，所以取余要用逆元取余
下面贴出两种可以用逆元取余的方法

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<iostream>

#include<cmath>

#include<stack>

#define mod 1000000007

using namespace std;

typedef long long ll;

ll qow(ll a,ll b) {

    ll ans = ;

    while( b ) {

        if( b& ) {

            ans = ans*a%mod;

        }

        a = a*a%mod;

        b /= ;

    }

    return ans;

}

int main() {

    ll T;

    cin >> T;

    while( T -- ) {

        ll n,m;

        cin >> n >> m;

        ll sum = ,num=;

        if( n ==  ) {

            cout << sum << endl;

            continue;

        }

        num = (qow(m,n+)-)*qow(m-,mod-)%mod; //费马小定理的求法

        /*用qow(m-1,mod-2)对m-1进行逆元取余*/

        cout << num << endl;

    }

    return ;

}

#include <cstdio>

#include <cmath>

#define MAX 100005

#define mod 1000000007

using namespace std;

long long multi(long long a, long long b)//快速幂

{

    long long ret = ;

    while(b > )

    {

        if(b & )

            ret = (ret * a) % mod;

        a = (a * a) % mod;

        b >>= ;

    }

    return ret;

}

long long exgcd(long long a, long long b, long long &x, long long &y)//扩展欧几里得

{

    if(!b)

    {

        x = ;

        y = ;

        return a;

    }

    long long d = exgcd(b, a % b, x, y);

    long long tmp = x;

    x = y;

    y = tmp - a / b * y;

    return d;

}

int main()

{

    int T;

    scanf("%d", &T);

    while(T--)

    {

        long long n, m, x, y;

        scanf("%lld %lld", &n, &m);

        long long mul = (multi(m, n + ) - ) % mod;

        long long d = exgcd(m - , mod, x, y);//若这里mod的位置填写mod * (m - 1),最终计算时需要让x和mod都除以d

        x *= mul;

        x /= d;//因为m - 1和mod是互质的，这句可以去掉。

        x = (x % mod + mod) % mod;//防止最终结果为负数

        printf("%lld\n", x);

    }

    return ;

}