题面 【分治|【模拟赛|ZROI】01串(容斥,分治FFT)】
文章图片
文章图片
文章图片
题解 前面的转化不重要,我就直接贴了(其实是因为我怎么努力都想不明白)
文章图片
然后我们将每两个数中间加分割线(两端还有两个,总共n + 1 n+1 n+1 个),每次选择了一个01 01 01 后就顺便把分割线也删了。分割线删除的时间就是一个排列,每个0 0 0 右边的分割线一定比左边的分割线早删, 1 1 1 相反, ? ? ? 随意。
所以我们就可以把01 01 01 转化成排列中相邻两个数的相对大小限制<
>
。然后就是个经典题了。
对于一个排列,相邻两个数有大于或小于的限制,怎么做?
我们的做法是容斥。先保留所有的<
符号,去掉>
符号的限制,计算总方案数。这时一个>
符号的限制不被满足,等价于原先的位置放上了<
符号。我们根据这点容斥,令d p [ i ] dp[i] dp[i] 表示考虑前i i i 个位置的方案数。
我们枚举排列 1~i 中最后一个逆序位置j ( p j > p j + 1 ) j(p_j>p_{j+1}) j(pj?>pj+1?) ,令p r o [ i ] = ( ? 1 ) i 之 前 > 符 号 的 个 数 pro[i]=(-1)^{i之前>符号的个数} pro[i]=(?1)i之前>符号的个数 , c [ i ] c[i] c[i] 表示i i i 和i + 1 i+1 i+1 之间的符号:
d p [ i ] = ∑ j < i , c [ j ] = ‘ > ’ d p [ j ] ? ( p r o [ j + 1 ] ? p r o [ i ] ) ? ( i j ) = i ! ? p r o [ i ] ∑ j < i , c [ j ] = ‘ > ’ d p [ j ] ? p r o [ j + 1 ] j ! ? 1 ( i ? j ) ! dp[i]=\sum_{j’} dp[j]\cdot (pro[j+1]\cdot pro[i])\cdot {i\choose j}\\ =i!\cdot pro[i]\sum_{j’} \frac{dp[j]\cdot pro[j+1]}{j!}\cdot \frac{1}{(i-j)!} dp[i]=j’∑?dp[j]?(pro[j+1]?pro[i])?(ji?)=i!?pro[i]j’∑?j!dp[j]?pro[j+1]??(i?j)!1?
我们用分治FFT(NTT)就好了,时间复杂度O ( n log ? 2 n ) O(n\log^2n) O(nlog2n) 。
CODE
#include
推荐阅读