ACM模版

描述

题解

很想要轻描淡写的告诉大家，在《具体数学》一书第六章第五节有“伯努利数”的详细讲解，但是感觉这又有些长篇大论讲得着实不错，但是对于第一次接触伯努利数并且数学不是特别好的人来说，实在是有些难以接受，于是我选择更加简单的，直接用结论吧。

这里很明显的用到了伯努利数，那么

∑i=1nik=1k+1∑i=1k+1Cik+1B[k+1−i](n+1)i

其中 B[i] 表示伯努利数， Cji 表示组合数，预处理出来这两个，就很容易获取最后的结果了。利用到如下两个公式：

B[n]=−1n+1∑k=0n−1Ckn+1B[k]
Cmn=Cmn−1+Cm−1n−1

剩下的也就没有什么了，先这样吧，以后继续深入了解这个神奇的数……目前《具体数学》这一部分看得还是懵懵懂懂，数学底子太差看得不顺心啊！

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 2222;
const int MOD = 1e9 + 7;

int k;
ll n;
int B[MAXN];
int inv[MAXN];
int C[MAXN][MAXN];

void init()
{
    C[0][0] = 1;
    for (int i = 1; i < MAXN; i++)
    {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
        {
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
        }
    }

    inv[1] = 1;
    for (int i = 2; i < MAXN; i++)
    {
        inv[i] = (ll)inv[MOD % i] * (MOD - MOD / i) % MOD;
    }

    B[0] = 1;
    for (int i = 1; i < MAXN; i++)
    {
        B[i] = 0;
        for (int k = 0; k < i; k++)
        {
            B[i] = (B[i] + (ll)C[i + 1][k] * B[k] % MOD) % MOD;
        }
        B[i] = ((ll)B[i] * (-inv[i + 1]) % MOD + MOD) % MOD;
    }
}

int main()
{
    init();

    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%lld%d", &n, &k);

        n++;
        n %= MOD;
        ll tmp = n, ans = 0;
        for (int i = 1; i <= k + 1; i++)
        {
            ans = (ans + (ll)C[k + 1][i] * B[k + 1 - i] % MOD * n % MOD) % MOD;
            n = (ll)n * tmp % MOD;
        }
        ans = (ll)ans * inv[k + 1] % MOD;

        printf("%lld\n", ans);
    }

    return 0;
}