JZOJ 5666 法力风暴

令 ai=Ai。
注意到 ∏i≠xai=n∏i=1ai−n∏i=1(ai−[i=x])，故转化为求 E(n∏i=1a′i)，其中 a′i 表示 ai 所有操作后的值。

令 bi=ai−a′i，则有 E(n∏i=1(ai−bi))=1nk∑b1+b2+⋯+bn=kk!n∏i=1bi!n∏i=1(ai−bi)=k!nk∑b1+b2+⋯+bn=kn∏i=1ai−bibi!

如果有点生成函数知识的话，容易发现这很像某些生成函数之积的 xk 项系数。
设指数生成函数 Gi(x)=∞∑j=1ai−jj!xj。
容易发现 Gi(x)=ex(ai−x)。
则 ∑b1+b2+⋯+bn=kn∏i=1ai−bibi!=(n∏i=1Gi(x))[xk]。

然后发现 n∏i=1Gi(x)=enxn∏i=1(ai−x)。
考虑用普通的分治思想 + NTT 来求 n∏i=1(ai−x)（并不是 CDQ 分治）。
（大常数选手被卡）

又因为 enx=∞∑i=0nixii!，得 (n∏i=1Gi(x))[xk]=n∑i=0nk−i(k−i)!fi，其中 fi=(n∏i=1(ai−x))[xi]。
看起来是不能做的，但是本来还有个系数 k!nk。
k!nkn∑i=0nk−i(k−i)!fi=n∑i=0k!nk(k−i)!fi

注意到 k!(k−i)! 只有 i 项，于是直接算即可（其实就是下降幂）
实际上 n∏i=1ai=f0，故要求的为 −n∑i=1k!nk(k−i)!fi。

代码：

#pragma GCC optimize("Ofast")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC diagnostic error "-std=c++14"
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC optimize("fast-math","unroll-loops","no-stack-protector","inline")
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1 << 18;
const int mod = 998244353;
const int G = 3;
const int Gi = 332748118;
int len,n = 1,k;
int fpow(int a,int b)
{
    int ret = 1;
    for(;b;b >>= 1)
        (b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
    return ret;
}
int a[N + 5],f[N + 5],omg[N + 5],inv[N + 5];
int ans;
void ntt(int *a,int *omg,int n,int lg)
{
    for(register int i = 0;i < n;++i)
    {
        int t = 0;
        for(register int j = 0;j < lg;++j)
            if(i & (1 << j))
                t |= (1 << lg - j - 1);
        if(i < t)
            swap(a[i],a[t]);
    }
    for(register int w = 2,m = 1;w <= n;w <<= 1,m <<= 1)
        for(register int i = 0;i < n;i += w)
            for(register int j = 0;j < m;++j)
            {
                int t = (long long)omg[n / w * j] * a[i + j + m] % mod;
                a[i + j + m] = (a[i + j] - t + mod) % mod,a[i + j] = (a[i + j] + t) % mod;
            }
}
void mul(int *a,int *b,int len)
{
    int lg = 0,n = 1;
    for(;n < len * 2;n <<= 1,++lg);
    for(register int i = 0;i < n;++i)
        omg[i] = fpow(G,(mod - 1) / n * i),inv[i] = fpow(Gi,(mod - 1) / n * i);
    ntt(a,omg,n,lg),ntt(b,omg,n,lg);
    for(register int i = 0;i < n;++i)
        a[i] = (long long)a[i] * b[i] % mod;
    ntt(a,inv,n,lg);
    int n_inv = fpow(n,mod - 2);
    for(register int i = 0;i < n;++i)
        a[i] = (long long)a[i] * n_inv % mod;
}
void solve(int l,int r,int L,int R)
{
    if(l == r)
    {
        if(l < len)
            f[L] = a[l] % mod,f[L + 1] = mod - 1;
        else
            f[L] = 1,f[L + 1] = 0;
        return ;
    }
    int mid = l + r >> 1,MID = L + R >> 1;
    solve(l,mid,L,MID);
    solve(mid + 1,r,MID + 1,R);
    static int buf[2][N + 5];
    for(register int i = 0;i <= R - L;++i)
        buf[0][i] = buf[1][i] = 0;
    for(register int i = 0;i <= mid - l + 1;++i)
        buf[0][i] = f[L + i],buf[1][i] = f[MID + 1 + i];
    mul(buf[0],buf[1],mid - l + 2);
    for(register int i = 0;i <= r - l + 1;++i)
        f[L + i] = buf[0][i];
}
int main()
{
    freopen("manastorm.in","r",stdin),freopen("manastorm.out","w",stdout);
    scanf("%d%d",&len,&k),k %= mod;
    for(;n < len;n <<= 1);
    for(register int i = 0;i < len;++i)
        scanf("%d",a + i);
    solve(0,n - 1,0,2 * n - 1);
    int n_inv = fpow(len,mod - 2);
    for(register int i = 1,prod = (long long)n_inv * k % mod;i <= len;prod = (long long)prod * n_inv % mod * (k - i) % mod,++i)
        ans = (ans - (long long)f[i] * prod % mod + mod) % mod;
    printf("%d\n",ans);
}