出题人题解 | #Friendly Polynomial#

原题解链接：https://ac.nowcoder.com/discuss/150246

设 $f [i]$ 表示长度为 $n$ 的不合法序列的数量

如果存在一个位置 $i$ 不合法,那么此时 $1 - i$ 的数恰好构成了一个 $1 - i$ 的排列

考虑直接递推计算，为了避免重复计算答案，我们去枚举最大的不满足条件的 $i$

比如序列{ $123456$ }在 $i = 2$ 或 $3$ 时都不满足条件,我们只在 $3$ 处计算贡献

一种的统计方法是,如果是最大的不满足条件的位置，那么 $i 十 1 n$ 位置的数构成的序列一定是合法的，方案数是 $f (n - i)$ ,乘法原理统计即可

因此不难得到递推式

$f(n)=\sum_{k=1}^{n-1} k ! * f(n-k)$

分治FFT / 多项式求逆即可

时间复杂度: $O\left(n \log ^{2} n\right)$

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
#define swap(x,y) (x ^= y, y ^= x, x ^= y)
#define mul(a, b) 1ll * a * b % P
#define add(a, b) (a + b >= P ? a + b - P : a + b)
#define dec(a, b) (a - b <  0 ? a - b + P : a - b)
#define rg register 
#define int long long 
const int MAXN = (1 << 21) + 10, P = 998244353, G = 3, Gi = 332748118; 
inline int read() { 
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}    
int N = 4 * 400050;
inline int fastpow(int a, int k) {
    int  base = 1;
    while(k) {
        if(k & 1) base = mul(a, base);
        a = mul(a, a); k >>= 1;
    }
    return base % P;
}
int r[MAXN], X[MAXN], Y[MAXN], A[MAXN], B[MAXN], Og[MAXN];
inline void NTT(int  *A, int type, int len) {
    int limit = 1, L = 0;
    while(limit < len) limit <<= 1, L++;
    for(rg int i = 0; i < limit; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (L - 1));    
    for(rg int i = 0; i < limit; i++) if(i < r[i]) swap(A[i], A[r[i]]);
    for(rg int mid = 1; mid < limit; mid <<= 1) {    
        int  R = mid << 1;
        int  W = fastpow(G, (P - 1) / R); Og[0] = 1;
        for(rg int j = 1; j < mid; j++) Og[j] = mul(Og[j - 1], W);
        for(rg int j = 0; j < limit; j += R) {
            for(rg int k = 0; k < mid; k++) {
                 const int x = A[j + k], y = mul(Og[k], A[j + k + mid]);
                 A[j + k] = add(x, y), A[j + k + mid] = dec(x, y);
            }
        }
    }
    if(type == -1) {
        std::reverse(&A[1], &A[limit]);
        for(int i = 0, inv = fastpow(len , P - 2); i < limit; i++)
            A[i] = 1ll * A[i] * inv % P;
    }
}
void Inv(int *a, int *b, int len) {
    if(len == 1) {
        b[0] = fastpow(a[0], P - 2);
        return ;
    }
    Inv(a, b, len >> 1);
    for(rg int i = 0; i < len; i++) A[i] = a[i], B[i] = b[i];
    NTT(A, 1, len << 1); NTT(B, 1, len << 1);
    for(rg int i = 0; i < (len << 1); i++) A[i] = mul(mul(A[i], B[i]), B[i]) ;
    NTT(A, -1, len << 1);
    for(rg int i = 0; i < len; i++) b[i] = (1ll * (b[i] << 1) % P + P - A[i] ) % P;
}
signed main() {
    X[0] = 1;
    for(int i = 1; i < N; i++) X[i] = (X[i - 1] * i) % P;
       Inv(X, Y, 262144);
       int T = read();
       while(T--) {
		int x = read();
		printf("%lld\n", (X[x] + Y[x] % P + P) % P);
    }
    return 0;
}
/*
4
3
5
233
12345
*/