P5825 排列计数 加强版

加强版和原题不同之处在于 \(p\) 不再是一个排列，而是一个普通的值域为 \([1,n]\) 的数组

考虑将 \([p_i <p_{i+1}]\) 转化为 \(1-[p_i \ge p_{i+1}]\)，方便计算后面的 \(g\)，也就是恰好 \(n-k-1\) 不上升点的方案数

记一段不上升点的连续段为非升段，\(f_i\) 表示恰好 \(i\) 个不上升点的方案数，即将序列划分为 \(n-i\) 段非升段的方案数

由于恰好不好计算，考虑二项式反演，记 \(g_i\) 表示钦定 \(i\) 段非升段的方案数

那么 \(f_i=\sum\limits_{i=j}^{n-1} \tbinom{j}{i} (-1)^{j-i} g_{n-j}\)

由于只要确定了数集便能确定整个序列，那么相当于要把 \(p\) 划分为 \(n-i\) 个数集，可以枚举每一种数，然后直接把它们的方案数乘起来，但是这样可能会出现空集，那么再来容斥一下

记 \(h_i\) 表示钦定 \(i\) 段可为空集的非升段的方案数，那么 \(h_i=\prod\limits_{j=1}^n \tbinom{i+c_j-1}{i-1}\)（\(c_j\) 个球放入 \(i\) 个盒子），\(c\) 为每种数字的出现次数

那么 \(g_i=\sum\limits_{j=0}^i \tbinom{i}{j} (-1)^j h_{i-j}\)，组合数是强制先选择 \(j\) 个空集

考虑快速计算 \(f,g,h\)，可以发现 \(f,g\) 拆掉组合数之后，\(g\) 再反转一下就是标准的卷积，\(\text{ntt}\) 优化即可，而 \(h\) 可以发现本质不同的 \(c\) 只有 \(\text{O}(\sqrt n)\) 个，直接套一个快速幂即可，某位大佬表示算上快速幂这部分的复杂度还是 \(\text{O}(\sqrt n)\)

#include<bits/stdc++.h>
using namespace std;
#define poly vector<long long>
#define fix(f,n) f.resize(n+1)
#define c(n,m) (n<m||m<0||n<0?0:fac[n]*ifac[m]%mod*ifac[n-(m)]%mod)
int n,x,cnt[500001],num[500001],rev[3000001],w[3000001];
long long ans[500001],fac[1000001],ifac[1000001],inv[1000001];
const int mod=998244353;
auto qpow(long long a,long long b){
    long long res=1;
    for(;b;b>>=1,a=a*a%mod) if(b&1) res=res*a%mod;
    return res;
}
void init(int n,int m){
    fac[0]=ifac[0]=inv[1]=w[n]=1,w[n|1]=qpow(3,(mod-1)/n);
    for(int i=2;i<n;i++) w[n|i]=1ll*w[n|i-1]*w[n|1]%mod;
    for(int i=n-1;i>=1;i--) w[i]=w[i<<1];
    for(int i=2;i<=m;i++) inv[i]=inv[mod%i]*(mod-mod/i)%mod;
    for(int i=1;i<=m;i++) fac[i]=fac[i-1]*i%mod,ifac[i]=ifac[i-1]*inv[i]%mod;
}
void ntt(poly &f,int c,int n){
    fix(f,n-1);
    for(int i=0;i<n;i++) if(i<rev[i]) swap(f[i],f[rev[i]]);
    for(int k=2;k<=n;k<<=1){
        for(int i=0;i<n;i+=k){
            for(int j=i,*p=w+k;j<i+(k>>1);j++){
                int x=f[j],y=f[j+(k>>1)]*(*p++)%mod;
                f[j+(k>>1)]=(x-y+mod)%mod;
                f[j]=(x+y)%mod;
            }
        }
    }
    if(!c) reverse(f.begin()+1,f.begin()+n);
}
poly operator*(poly f,poly g){
    int m=f.size()+g.size()-2,n=1<<__lg(m)+1,p=0;
    for(int i=0;i<n;i++) rev[i]=(rev[i>>1]>>1)|(i&1?n>>1:0);
    ntt(f,1,n),ntt(g,1,n),p=qpow(n,mod-2);
    for(int i=0;i<n;i++) f[i]=f[i]*g[i]%mod;
    ntt(f,0,n),fix(f,m);
    for(int i=0;i<=m;i++) f[i]=f[i]*p%mod;
    return f;
}
int main(){
	scanf("%d",&n),init(1<<20,n*2);
    for(int i=1;i<=n;i++) scanf("%d",&x),cnt[x]++;
    poly s,k,f(n),g(n+1),h(n+1,1);
    h[0]=0;
    for(int i=1;i<=n;i++) if(cnt[i]) num[cnt[i]]++;
    for(int i=1;i<=n;i++) if(num[i]) s.push_back(i);
    for(int i=1;i<=n;i++) for(auto j:s) h[i]=h[i]*qpow(c(i+j-1,i-1),num[j])%mod;
    for(int i=0;i<=n;i++) g[i]=i&1?mod-ifac[i]:ifac[i],h[i]=h[i]*ifac[i]%mod;
    k=g*h,fix(g,n-1);
    for(int i=1;i<=n;i++) g[n-i]=k[i]*fac[i]%mod;
    for(int i=0;i<n;i++) f[n-1-i]=i&1?mod-ifac[i]:ifac[i];
    for(int i=0;i<n;i++) g[i]=g[i]*fac[i]%mod;
    f=f*g;
    for(int i=0;i<n;i++) ans[i]=ifac[i]*f[n-1+i]%mod;
    for(int i=0;i<n;i++) printf("%lld ",ans[n-i-1]);
	return 0;
}