【学习笔记】[AGC060D] Same Descent Set

2024-01-02 20:29:45

本来是想做点多项式调节一下,结果发现这玩意太肝了,似乎并没有起到调节作用。

f ( S ) f(S) f(S)表示符号为 < < <的下标集合恰好 S S S的方案数,因为两个序列完全等同,因此答案等于

∑ S ? { 1 , 2 , . . . , n ? 1 } f ( S ) 2 \sum_{S\subseteq \{1,2,...,n-1\}}f(S)^2 S?{1,2,...,n?1}?f(S)2

显然,如果如果同时存在 < < < > > >符号则不好处理,考虑钦定一些位置为 < < <,其他位置任意,可以得到计算式:

f ( S ) = ∑ S ? T ( ? 1 ) ∣ T ∣ ? ∣ S ∣ ( n l 1 , l 2 , . . . , l k ) f(S)=\sum_{S\subseteq T}(-1)^{|T|-|S|}\binom{n}{l_1,l_2,...,l_k} f(S)=S?T?(?1)T?S(l1?,l2?,...,lk?n?)

其中 ∑ l i = n \sum l_i=n li?=n,表示所有用 < < <符号连接起来的极长段。方便起见,将其记作 g ( T ) g(T) g(T)

大力化式子:

∑ S ∑ S ? T 1 ∑ S ? T 2 ( ? 1 ) ∣ T 1 ∣ + ∣ T 2 ∣ g ( T 1 ) g ( T 2 ) = ∑ T 1 ∑ T 2 ( ? 1 ) ∣ T 1 ∣ + ∣ T 2 ∣ 2 ∣ T 1 ∩ T 2 ∣ g ( T 1 ) g ( T 2 ) = 2 n ? 1 ∑ T 1 ∑ T 2 1 ( ? 2 ) ∣ T 1 ∣ 1 ( ? 2 ) ∣ T 2 ∣ 2 ∣ T 1 ∩ T 2 ∣ g ( T 1 ) g ( T 2 ) \begin{aligned}\sum_S\sum_{S\subseteq T_1}\sum_{S\subseteq T_2}(-1)^{|T_1|+|T_2|}g(T_1)g(T_2)&=\sum_{T_1}\sum_{T_2}(-1)^{|T_1|+|T_2|}2^{|T_1\cap T_2|}g(T_1)g(T_2)\\&=2^{n-1}\sum_{T_1}\sum_{T_2}\frac{1}{(-2)^{|T_1|}}\frac{1}{(-2)^{|T_2|}} 2^{|T_1\cap T_2|}g(T_1)g(T_2)\end{aligned} S?S?T1??S?T2??(?1)T1?+T2?g(T1?)g(T2?)?=T1??T2??(?1)T1?+T2?2T1?T2?g(T1?)g(T2?)=2n?1T1??T2??(?2)T1?1?(?2)T2?1?2T1?T2?g(T1?)g(T2?)?

其中第二步是枚举 T 1 , T 2 T_1,T_2 T1?,T2?的补集,也就是分界点。 T 1 ∩ T 2 T_1\cap T_2 T1?T2?就是共同的分界点

先枚举共同的分界点(注意这一步的系数即为 2 ∣ T 1 ∩ T 2 ∣ 2^{|T_1\cap T_2|} 2T1?T2?),在分界点之间可能进一步划分成更小的段,容易看出这是将一些元素(实际上一些段)“排列”起来,因此设每一小段的 E G F EGF EGF

A ( x ) = ∑ i ≥ 1 ? 1 2 i ! x i A(x)=\sum_{i\ge 1}-\frac{1}{2i!}x^i A(x)=i1??2i!1?xi

则一段的 G F GF GF

B ( x ) = 1 1 ? A ( x ) B(x)=\frac{1}{1-A(x)} B(x)=1?A(x)1?

最后将这些段再次排列起来,答案是

C ( x ) = 1 1 ? B ( x ) C(x)=\frac{1}{1-B(x)} C(x)=1?B(x)1?

只需两次多项式求逆即可。注意计数的对象是两个,因此 B ( x ) B(x) B(x)的每一项系数应当平方,并且最终提取系数时要成上 ( n ! ) 2 × 2 n + 1 (n!)^2\times 2^{n+1} (n!)2×2n+1

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);    
    cin>>n,len=1;while(len<=n)len<<=1;init(len<<1);
    f.a.resize(len);for(int i=1;i<len;i++)f.a[i]=(mod+1>>1)*inv[i]%mod;
    f.a[0]=1;f=Inv(f,len);
    for(int i=1;i<len;i++)f.a[i]=-f.a[i]*f.a[i]%mod;
    f.a[0]=1;f=Inv(f,len);
    cout<<(f.a[n]*fac[n]%mod*fac[n]%mod*fpow(2,n+1)%mod+mod)%mod;
}

文章来源:https://blog.csdn.net/cqbzlydd/article/details/135348011
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。