自己切片视频做网站,wordpress登陆地址,网站推广思路,有别墅的件怎么写者本来是想做点多项式调节一下#xff0c;结果发现这玩意太肝了#xff0c;似乎并没有起到调节作用。
设 f ( S ) f(S) f(S)表示符号为 的下标集合恰好为 S S S的方案数#xff0c;因为两个序列完全等同#xff0c;因此答案等于 ∑ S ⊆ { 1 , 2 , . . . , n …本来是想做点多项式调节一下结果发现这玩意太肝了似乎并没有起到调节作用。
设 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,...,lkn)
其中 ∑ l i n \sum l_in ∑lin表示所有用 符号连接起来的极长段。方便起见将其记作 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∣2∣T1∩T2∣g(T1)g(T2)2n−1T1∑T2∑(−2)∣T1∣1(−2)∣T2∣12∣T1∩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|} 2∣T1∩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)i≥1∑−2i!1xi
则一段的 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^{n1} (n!)2×2n1。
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0); cinn,len1;while(lenn)len1;init(len1);f.a.resize(len);for(int i1;ilen;i)f.a[i](mod11)*inv[i]%mod;f.a[0]1;fInv(f,len);for(int i1;ilen;i)f.a[i]-f.a[i]*f.a[i]%mod;f.a[0]1;fInv(f,len);cout(f.a[n]*fac[n]%mod*fac[n]%mod*fpow(2,n1)%modmod)%mod;
}
