记录编号	255298	评测结果	AAAAAAAAAA
题目名称	[HEOI 2016] 求和	最终得分	100
用户昵称	Owaski	是否通过	通过
代码语言	C++	运行时间	1.171 s
提交时间	2016-04-27 12:56:40	内存使用	7.18 MiB

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

const int N = 3e5;
const int MOD = 998244353;

int n;
int fac[N+9], inv[N+9];
int g[N+9];
int A[N+9], B[N+9];
int ans;

inline int fpm(int a, int b) {
    int ret = 1;
    while(b) {
        if(b&1) ret = 1ll*ret*a%MOD;
        a = 1ll*a*a%MOD, b >>= 1;
    }
    return ret;
}

inline void DFT(int A[], int n, int f) {
    for(int i = 0; i < n; ++i) {
        int p = 0, s = i;
        for(int j = 1; j < n; j <<= 1)
            p = p<<1|(s&1), s >>= 1;
        if(p > i) std::swap(A[i], A[p]);
    }
    static int r, wn, w[N+9];
    r = 3, wn = fpm(r, (MOD-1)/n), w[0] = w[n] = 1;
    for(int i = 1; i < n; ++i) w[i] = 1ll*w[i-1]*wn%MOD;
    for(int l = 2; l <= n; l <<= 1)
        for(int i = 0; i < n; i += l)
            for(int j = 0; j < (l>>1); ++j) {
                int u = A[i+j], v = 1ll*A[i+j+(l>>1)]*(f==1?w[n/l*j]:w[n-n/l*j])%MOD;
                A[i+j] = (u+v)%MOD, A[i+j+(l>>1)] = (u-v+MOD)%MOD;
            }
    if(f == -1) {
        int invn = fpm(n, MOD-2);
        for(int i = 0; i < n; ++i)
            A[i] = 1ll*A[i]*invn%MOD;
    }
}

int main() {
    freopen("heoi2016_sum.in", "r", stdin);
    freopen("heoi2016_sum.out", "w", stdout);

    std::cin >> n;
    fac[0] = inv[0] = 1;
    for(int i = 1; i <= n; ++i) {
        fac[i] = 1ll*fac[i-1]*i%MOD;
        inv[i] = fpm(fac[i], MOD-2);
    }
    g[1] = n;
    for(int i = 2; i <= n; ++i)
        g[i] = 1ll*(fpm(i, n+1)-i+MOD)*fpm(i-1, MOD-2)%MOD;
    for(int i = 0; i <= n; ++i) {
        A[i] = (i&1)?MOD-inv[i]:inv[i];
        B[i] = 1ll*g[i]*inv[i]%MOD;
    }
    int _n = 1;
    while(_n <= 2*n) _n <<= 1;
    DFT(A, _n, 1), DFT(B, _n, 1);
    for(int i = 0; i < _n; ++i)
        A[i] = 1ll*A[i]*B[i]%MOD;
    DFT(A, _n, -1);
    ans = 1;
    for(int i = 1, j = 2; i <= n; ++i, j = (j<<1)%MOD)
        (ans += 1ll*j*fac[i]%MOD*A[i]%MOD) %= MOD;
    std::cout << ans << std::endl;
    
    fclose(stdin);fclose(stdout);
    return 0;
}