51nod1228 序列求和(自然数幂和)

与UVA766 Sum of powers类似，见http://www.cnblogs.com/IMGavin/p/5948824.html

由于结果对MOD取模，使用逆元

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<string>

#include<algorithm>

#include<map>

#include<queue>

#include<vector>

#include<cmath>

#include<utility>

using namespace std;

typedef long long LL;

const int N = 2016, INF = 0x3F3F3F3F, MOD = 1000000007;

LL bo[N];

LL cm[N][N], inv[N];

void init(){

    inv[1] = 1;

    for(int i = 2; i < N; i++){

    	inv[i] = (MOD - MOD / i ) * inv[MOD % i] % MOD;

    }

    memset(cm, 0, sizeof(cm));

    cm[0][0] = 1;

    for(int i = 1; i < N; i++){

        cm[i][0] = 1;

        for(int j = 1; j <= i; j++){

            cm[i][j] = (cm[i - 1][j - 1] + cm[i - 1][j]) % MOD;

        }

    }

    bo[0] = 1;

    for(int i = 1; i < N; i++){

        bo[i] = 0;

        for(int j = 0; j < i; j++){

        	bo[i] += cm[i + 1][j] * bo[j] % MOD;

        	bo[i] %= MOD;

        }

        bo[i] = (-bo[i] * inv[i + 1] % MOD + MOD) % MOD;

    }

    bo[1] = inv[2];

}

LL PowMod(LL a,LL b,LL MOD){//快速幂

    LL ret=1;

    while(b){

        if(b&1) ret=(ret*a)%MOD;

        a=(a*a)%MOD;

        b>>=1;

    }

    return ret;

}

LL solve(LL n, LL m){

	LL ans = 0;

	for(LL k = 0; k <= m; k++){

		ans += (cm[m + 1][k] * bo[k] % MOD) * PowMod(n % MOD, m + 1 - k, MOD) % MOD;

		ans %= MOD;

	}

	ans = ans * inv[m + 1] % MOD;

	return ans;

}

int main(){

    init();

    int t;

    cin >> t;

    while(t--){

        LL n, k;

        scanf("%I64d %I64d", &n, &k);

        printf("%I64d\n", solve(n, k));

    }

    return 0;

}