题解：P13909 「TFXOI Round 3」就此别过

· · 题解

看不懂官方题解。

显然二项式反演，定义 g_i 表示恰 i 个断点的方案数，f_i 为选定 i 个断点，剩余任意的方案数，有：

g_i=\sum_j (-1)^{i-j}{n-1-j\choose n-1-i}f_j

枚举多余断点，直接容斥易得，这一步可以卷积优化，比较平凡不再赘述。

考虑如何得到 f，注意到每一段若长度确定，要么上升要么下降，再枚举不同段的大小关系即可完全确定序列，但是对于长度为 1 的段会多算一遍，因为上升和下降没有区别。不妨要求 1 的段上升，对限制容斥可得：

f_i=\sum_j (-1)^j{i+1\choose j}{n-j-1\choose i-j}(i+1)!2^{i+1-j}

这里要特判 n 个长度为 1 的段的情况。注意到这也可以拆为一次卷积，时间复杂度 O(n\log n)，共两次卷积。

inline void solve(){
    cin>>n;
    for(int i=1;i<=n;i++) bas[i]=reduce(bas[i-1]<<1);
    for(int i=0;i<n;i++) a[i]=(i&1?Mod-ifac[i]:ifac[i])*fac[n-1-i]%Mod;
    for(int i=0;i<n;i++) b[i]=ifac[i+1]*ifac[i]%Mod*bas[i+1]%Mod;
    NTT::polymul(n-1,a,b,f);
    for(int i=0;i<n;i++) f[i]=f[i]*fac[i+1]%Mod*ifac[n-i-1]%Mod*fac[i+1]%Mod;
    f[n-1]=(f[n-1]+(n&1?Mod-1:1)*fac[n])%Mod;
    for(int i=0;i<n;i++) f[i]=(i&1?Mod-f[i]:f[i])*fac[n-1-i]%Mod;
    for(int i=0;i<n;i++) a[i]=ifac[i];
    NTT::polymul(n-1,f,a,g);
    for(int i=0;i<n;i++) cout<<(i&1?Mod-g[i]:g[i])*ifac[n-1-i]%Mod<<'\n';
}