题解：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)

，共两次卷积。

CPP

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';
}

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

文章操作

相关推荐

评论

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