「CF923E」Perpetual Subtraction

题目链接：https://codeforces.com/contest/923/problem/E。

首先假设原概率的生成函数为$F(x)=\sum_{i=0}^{n}f_ix^i$，那么一次操作之后显然会变成：

$$F^*(x)=\sum_{i=0}^{n}\sum_{j=i}^{n}\frac{f_j}{j+1}x^i$$

然后对这个式子进行一些魔幻的操作，先简单变一下：

$$\begin{align} F^*(x)&=\sum_{j=0}^{n}\frac{f_j}{j+1}\sum_{i=0}^{j}x^i\\ &=\sum_{j=0}^{n}\frac{f_j}{j+1}\frac{x^{j+1}-1}{x-1}\\ &=\frac{1}{x-1}\sum_{j=0}^{n}f_j\frac{x^{j+1}-1}{j+1}\\ \end{align}$$

注意后面那一项看起来就很像积分公式，套进去试试：

$$\begin{align} F^*(x)&=\frac{1}{x-1}\sum_{j=0}^{n}f_j\int_1^xt^j{\rm d}t\\ &=\frac{\int_1^xF(t){\rm d}t}{x-1} \end{align}$$

上面那个积分下限是$1$，而且分母是$x-1$，看起来就很不爽，没法继续变了。

可以设$G(x)=F(x+1)$，那么可以得到：

$$G^*(x)=\frac{\int_1^{x+1}F(t){\rm d}t}{x}=\frac{\int_0^{x}G(t){\rm d}t}{x}$$

这一来式子就简单多了，第$i$项变化之后可以很方便的写出来：

$$g^*_i=\frac{g_i}{i+1}$$

那么变$m$次之后就是：

$$g^*_i=\frac{g_i}{(i+1)^m}$$

最后就只需要考虑如何在$F,G​$之间转换了：

$$G(x)=\sum_{i=0}^{n}f_i(x+1)^i=\sum_{i=0}^{n}f_i\sum_{j=0}^{i}\binom{i}{j}x^j$$

也就是说：

$$g_i=\sum_{j=i}^{n}\binom{j}{i}f_j\\i!g_i=\sum_{j=i}^{n}\frac{j!f_j}{(j-i)!}$$

所以直接上$\rm NTT$就好了，换个方向也是同理。

复杂度$O(n\log n)$。

#include<bits/stdc++.h>
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 998244353;

int f[maxn],g[maxn],n,w[maxn],N,bit,pos[maxn],fac[maxn],ifac[maxn];
ll m;

int qpow(int a,int x) {
    int res=1;
    for(;x;x>>=1,a=1ll*a*a%mod) if(x&1) res=1ll*res*a%mod;
    return res;
}

void init() {
    for(N=1,bit=-1;N<=n<<1;N<<=1,bit++);
    for(int i=1;i<N;i++) pos[i]=pos[i>>1]>>1|((i&1)<<bit);
    w[0]=1,w[1]=qpow(3,(mod-1)/N);
    for(int i=2;i<N;i++) w[i]=1ll*w[i-1]*w[1]%mod;
    fac[0]=ifac[0]=1;
    for(int i=1;i<=N;i++) fac[i]=1ll*fac[i-1]*i%mod;
    ifac[N]=qpow(fac[N],mod-2);
    for(int i=N-1;i;i--) ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
}

void ntt(int *r,int op) {
    for(int i=1;i<N;i++) if(pos[i]>i) swap(r[i],r[pos[i]]);
    for(int i=1,d=N>>1;i<N;i<<=1,d>>=1)
        for(int j=0;j<N;j+=i<<1)
            for(int k=0;k<i;k++) {
                int x=r[j+k],y=1ll*w[k*d]*r[i+j+k]%mod;
                r[j+k]=(x+y)%mod,r[i+j+k]=(x-y+mod)%mod;
            }
    if(op==-1) {
        int d=qpow(N,mod-2);reverse(r+1,r+N);
        for(int i=0;i<N;i++) r[i]=1ll*r[i]*d%mod;
    }
}

int main() {
    read(n);scanf("%lld",&m);init();
    for(int i=0;i<=n;i++) read(f[i]),f[i]=1ll*f[i]*fac[i]%mod,g[i]=ifac[i];
    reverse(f,f+n+1);ntt(f,1),ntt(g,1);
    for(int i=0;i<N;i++) g[i]=1ll*f[i]*g[i]%mod;
    ntt(g,-1);
    reverse(g,g+n+1);
    for(int i=0;i<=n;i++) g[i]=1ll*g[i]*ifac[i]%mod;
    for(int i=n+1;i<N;i++) g[i]=0;
    for(int i=0;i<=n;i++) g[i]=1ll*g[i]*qpow(qpow(i+1,m%(mod-1)),mod-2)%mod;
    for(int i=0;i<N;i++) f[i]=0;
    for(int i=0;i<=n;i++) f[i]=1ll*ifac[i]*(i&1?mod-1:1)%mod,g[i]=1ll*g[i]*fac[i]%mod;
    reverse(g,g+n+1);ntt(f,1),ntt(g,1);
    for(int i=0;i<N;i++) f[i]=1ll*f[i]*g[i]%mod;
    ntt(f,-1);reverse(f,f+n+1);
    for(int i=0;i<=n;i++) printf("%d ",1ll*f[i]*ifac[i]%mod);puts("");
    return 0;
}