博客

题目链接：

哆啦A梦传送门

题意：求

题解：

因为这里多测试案例很多，一般方法 O(k^2)会T。

故我们用

伯努利数

公式，O(k)解决。

公式描述如下

可以看出只要我们预处理出每一项，就可以在线性时间内求得自然数的幂和。前面的倒数可以用递推法求逆元

预处理，组合数也可以预处理，



也可以先预处理，现在关键是如何预处理伯努利数。

伯努利数满足条件




，且有

那么继续得到

这就是伯努利数的递推式，逆元部分同样可以预处理。

代码：

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

using namespace std;

typedef long long LL;
const int maxn=2010;
const LL mod=1000000007;

LL C[maxn][maxn];
LL B[maxn],inv[maxn],jie[maxn];
LL temp[maxn];
LL n;


void init()
{
    int N=2002;

    ///线性筛逆元
        inv[1] = 1;
    for(int i=2; i<N; i++)
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;


    ///杨辉三角求组合数
    for(int i=0;i<N;i++)
    {
        C[i][0]=C[i][i]=1;
        for(int j=1;j<i;j++)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    }

    ///预处理伯努利数
    B[0]=1;
    for(int i=1;i<N;i++)
    {
        LL ans=0;
        for(int j=0;j<i;j++)
        {
            ans+=C[i+1][j]*B[j];
            ans%=mod;
        }
        ans*=-inv[i+1];
        ans=(ans%mod+mod)%mod;
        B[i]=ans;
    }

//    for(int i=1;i<=10;i++)
//        printf("%lld\n",B[i]);
}

int main()
{
    init();

    int ncase;
    scanf("%d",&ncase);

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

        n=n%mod;
        temp[0]=1;
        for(int i=1;i<=k+1;i++){
            temp[i]=temp[i-1]*(n+1)%mod;
        }

        LL sum=0;
        for(int i=1;i<=k+1;i++)
        {
            sum=sum+C[k+1][i]*B[k+1-i]%mod*temp[i]%mod;
            sum%=mod;
//            printf("sum=%lld\n",sum);
        }
        sum=sum*inv[k+1]%mod;
        printf("%lld\n",sum%mod);

    }
    return 0;




    return 0;
}