[TJOI/HEOI2016] 求和

$f(n) = \sum_i^n\sum_j^iS(i,j)\times 2^j \times j!\\ \Rightarrow f(n) = \sum_i^n\sum_j^nS(i,j)\times 2^j\times j!\\ \Rightarrow \sum_j^n 2^j\times j!\sum_iS(i,j)\\ \Rightarrow \sum_j^n2^j\times j!\times g_i$
$g_n = \sum_i^n S(i,j)\\ \Rightarrow \frac{1}{j!}\sum_i^n (-1)^i {j \choose i} (j-i)^n \\ \Rightarrow \sum_i^n\frac{(-1)^i}{i!}\frac{\sum_k^n(j-i)^k}{(j-i-1)(j-i)!}\\ \Rightarrow \sum_i^n\frac{(-1)^i}{i!}\times \frac{(j-i)^n-1}{(j-i-1)(j-i)!}$
所以我们现在可以 $O(n\log n)$ 求出 $g_i$ 了。因为后面的式子已经是卷积形式了 $A(i)*B(j-i)$ 了。

代码

#include<bits/stdc++.h>
using namespace std;
const int p = 998244353,Gi = 3,N = 1e6 + 10;
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return f ? -x : x;
}
int A[N],B[N],R[N],limit = 1,L,n;
int fac[N],ifac[N];
int qpow(int a,int b) {
    int x = 1;for(;b;b>>=1,a = 1LL * a * a % p) {
        if(b&1) x = 1LL * a * x % p;
    } return x;
}
void ntt(int *a,int type) {
    for(int i = 0;i < limit;i++) if(i > R[i]) swap(a[i],a[R[i]]);
    for(int mid = 1;mid < limit;mid <<= 1) {
        int wn = qpow(Gi,(p-1)/(mid<<1));
        for(int i = 0;i < limit;i += (mid<<1)) {
            for(int j = 0,w = 1;j < mid;j++,w = 1LL * w * wn % p) {
                int x = a[i+j],y = 1LL * a[j+i+mid] * w % p;
                a[i+j] = (x + y) % p;
                a[i+j+mid] = (p + x - y) % p; 
            }
        } 
    }
    if(type == -1) {
        reverse(a+1,a+limit);int inv = qpow(limit,p-2);
        for(int i = 0;i < limit;i++) a[i] = 1LL * a[i] * inv % p;
    }
} 
signed main()
{
    n = read();fac[0] = 1;
    for(int i = 1;i <= n;i++) fac[i] = 1LL * fac[i-1] * i % p;
    ifac[n] = qpow(fac[n],p - 2);
    for(int i = n - 1;i >= 0;i--) ifac[i] = 1LL * ifac[i+1] * (i+1) % p;
//    for(int i = 1;i <= n;i++) cout << ifac[i] << endl;
    B[1] = n + 1;A[0] = B[0] = 1;
    for(int i = 1;i <= n;i++) A[i] = 1LL * qpow(p-1,i) * ifac[i] % p;
    for(int i = 2;i <= n;i++) B[i] = 1LL * (qpow(i,n+1)-1+p)%p*(1LL*qpow(i-1,p-2)*ifac[i]%p)%p;
    while(limit <= n + n) limit <<= 1,L++;
    for(int i = 0;i < limit;i++) R[i] = (R[i>>1]>>1)|((i&1)<<L-1);
    ntt(A,1);ntt(B,1);
    for(int i = 0;i < limit;i++) A[i] = (1LL * A[i] * B[i]) % p;
    ntt(A,-1);
    int ans = 0;
    for(int i = 0,j = 1;i <= n;i++,j = 2LL * j % p) {
        ans = (ans + 1LL * j * fac[i] % p * A[i] % p) % p;
    }
    cout << ans << endl;
    return 0;
}