zcmimi's blog

https://www.51nod.com/Challenge/Problem.html#problemId=1822

定义

\begin{cases} B_0=1\\~\\ \displaystyle \sum\limits_{i=0}^n {n+1\choose i}B_i=0,n>0 \end{cases}

普通计算

\displaystyle B_n=-\frac 1{n+1} \sum_{i=0}^{n-1}{n+1\choose i}B_i

复杂度: O(n^2)

高效计算

推式子:

代入n=n+1:

\sum_{i=0}^n {n\choose i}B_i=B_n,n>1 \\~\\ \sum_{i=0}^n \frac{B_i}{i!(n-i)!}=\frac{B_n}{n!},n>1

0!=1,n=0时,也满足上述式子

\sum_{i=0}^n \frac{B_i}{i!} \cdot \frac 1{(n-i)!}=\frac{B_n}{n!},n\neq 1

算出n=1的情况:

\sum_{i=0}^n \frac{B_i}{i!} \cdot \frac 1{(n-i)!}=\frac{B_n}{n!}+[n=1]

构建生成函数

\sum_{n=0}^{\infty}\sum_{i=0}^n \frac{B_i}{i!} x^i \cdot \frac 1{(n-i)!} x^{n-i}=\sum_{n=0}^{\infty} \left( \frac{B_n}{n!}+[n=1]\right)x^n \\~\\ B(x)e^x=B(x)+x \\~\\ B(x)=\frac x{e^x-1} \\~\\ \begin{aligned} B(x) &=\frac x{\sum_{i=0}^{\infty} \frac{x^i}{i!}-1}\\ &=\frac 1{\sum_{i=0}^{\infty} \frac{x^i}{(i+1)!}} \end{aligned}

多项式求逆即可

性质

\displaystyle \sum_{i=1}^{n-1} i^k=\frac 1{k+1} \sum_{i=1}^{k+1} {k+1\choose i}B_in^{k-i+1}

51nod 1228 序列求和

#include<bits/stdc++.h>
const int N=2011,P=1000000007;
typedef long long ll;
int fac[N],inv[N],ifac[N],B[N];
int pw(int x,int b){
    int res=1;
    while(b){
        if(b&1)res=1ll*res*x%P;
        b>>=1;x=1ll*x*x%P;
    }
    return res;
}
void mod(int&x){if(x>=P)x-=P;}
void prep(int n){
    fac[0]=fac[1]=inv[0]=inv[1]=ifac[0]=ifac[1]=B[0]=1;
    for(int i=2;i<=n;++i)
        fac[i]=1ll*fac[i-1]*i%P,
        inv[i]=1ll*inv[P%i]*(P-P/i)%P,
        ifac[i]=1ll*ifac[i-1]*inv[i]%P;
    for(int i=1;i<=n;++i)
        for(int j=0;j<i;++j)
            mod(B[i]+=P-1ll*fac[i]*ifac[j]%P*ifac[i+1-j]%P*B[j]%P);
}
int S(ll t,int k){
    int n=(t+1)%P,ans=0;
    for(int i=0;i<=k;++i)
        mod(ans+=1ll*fac[k]*ifac[i]%P*ifac[k+1-i]%P*B[i]%P*pw(n,k+1-i)%P);
    return ans;
}
int main(){
    int T,k;ll n;
    scanf("%d",&T);
    prep(2001);
    while(T--)
        scanf("%lld%d",&n,&k),
        printf("%d\n",S(n,k));
}

51nod 1258 序列求和V4

伯努利数与自然数幂和
comment评论
Search
search