M_sea

洛谷4091 [HEOI2016/TJOI2016]求和
LuoguBZOJ分析$\large f(n)=\sum\limits_{i=0}^n\sum\limits_{j...
扫描右侧二维码阅读全文
29
2018/12

洛谷4091 [HEOI2016/TJOI2016]求和

Luogu

BZOJ

分析

$\large f(n)=\sum\limits_{i=0}^n\sum\limits_{j=0}^iS(i,j)\times 2^j\times (j!)$
$\large\qquad\ =\sum\limits_{i=0}^n\sum\limits_{j=0}^nS(i,j)\times2^j\times(j!)$
$\large\qquad\ =\sum\limits_{j=0}^n2^j\times(j!)\sum\limits_{i=1}^nS(i,j)$
$\large\qquad\ =\sum\limits_{j=0}^n2^j\times(j!)\sum\limits_{i=0}^n\sum\limits_{k=0}^j(-1)^k\times\frac{1}{k!(j-k)!}\times(j-k)^i$
$\large\qquad\ =\sum\limits_{j=0}^n2^j\times(j!)\sum\limits_{k=0}^j(-1)^k\times\frac{1}{k!(j-k)!}\sum\limits_{i=0}^n(j-k)^i$

设$\large g(j)=\sum\limits_{k=0}^j(-1)^k\times\frac{1}{k!(j-k)!}\sum\limits_{i=0}^n(j-k)^i$。

$\large f(n)=\sum\limits_{j=0}^n2^j\times(j!)\times g(j)$

考虑$g(\,)$怎么求。

$\large g(i)=\sum\limits_{j=0}^i(-1)^j\times\frac{1}{j!(i-j)!}\sum\limits_{k=0}^n(i-j)^k$
$\large\qquad\,=\sum\limits_{j=0}^i\frac{(-1)^j}{j!}\times\frac{\sum\limits_{k=0}^n(i-j)^k}{(i-j)!}$

再设$\large a(i)=\frac{(-1)^i}{i!},b(i)=\frac{\sum\limits_{k=0}^ni^k}{i!}=\frac{i^{n+1}-1}{(i-1)i!}$

所以$g(i)=\sum\limits_{j=1}^na(j)b(i-j)$

用$\mathrm{NTT}$算出$g(\,)$即可。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=400000+10;
const int P=998244353,G=3,Gi=332748118;

int n;
int r[MAXN];
int a[MAXN],b[MAXN];
int g[MAXN],inv[MAXN],fact[MAXN];

inline int FastPow(int a,int b) {
    re int ans=1;
    for (;b;b>>=1,a=a*a%P)
        if (b&1) ans=ans*a%P;
    return ans;
}

inline void NTT(int* a,int type,int limit) {
    for (re int i=0;i<limit;++i)
        if (i<r[i]) swap(a[i],a[r[i]]);
    for (re int i=1;i<limit;i<<=1) {
        int rot=FastPow(type==1?G:Gi,(P-1)/(i<<1));
        for (re int j=0;j<limit;j+=(i<<1)) {
            int w=1;
            for (re int k=0;k<i;++k,w=(w*rot)%P) {
                int x=a[j+k],y=w*a[j+k+i]%P;
                a[j+k]=(x+y)%P,a[j+k+i]=(x-y+P)%P;
            }
        }
    }
}

inline void Mul(int* a,int* b,int n) {
    int limit=1,l=0;
    for (;limit<=(n<<1);limit<<=1,++l);
    for (re int i=0;i<limit;++i)
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    NTT(a,1,limit); NTT(b,1,limit);
    for (re int i=0;i<limit;++i) a[i]=a[i]*b[i]%P;
    NTT(a,-1,limit);
    for (re int i=0,invn=FastPow(limit,P-2);i<=n;++i) g[i]=a[i]*invn%P;
}

mainint main() {
    n=read();
    b[0]=fact[0]=inv[0]=1,b[1]=n+1;
    for (re int i=1;i<=n;++i) fact[i]=fact[i-1]*i%P,inv[i]=FastPow(fact[i],P-2);
    for (re int i=0;i<=n;++i) a[i]=FastPow(P-1,i)*inv[i]%P;
    for (re int i=2;i<=n;++i) b[i]=(FastPow(i,n+1)-1)*FastPow(i-1,P-2)%P*inv[i]%P;
    Mul(a,b,n);
    int ans=0;
    for (re int i=0,pw=1;i<=n;++i,pw=(pw<<1)%P)
        ans=(ans+g[i]*pw%P*fact[i]%P)%P;
    printf("%lld\n",ans);
    fclose(stdin); fclose(stdout);
    return 0;
}
最后修改:2019 年 05 月 26 日 03 : 52 PM

发表评论