E. Falfa with Substring
Solution
考虑容斥，设Gn,k表示长度为n的字符串中有至少k个bit子串的方案数， 则有
Gn,k=(n−2kk)26n−3k
那么根据容斥原理，可以推出Fn,k和Gn,k的关系如下
Fn,k=j≥k∑(−1)j−k(jk)Gn,j=j≥k∑(−1)j−kk!(j−k)!j!Gn,j
为了方便起见，将与j无关的项移到左边，得到
k!Fn,k=j≥k∑(j−k)!(−1)j−kj!Gn,j
令
Hn,i=(n−i)!(−1)n−i
则化为
k!Fn,k=j≥k∑Hn,n−j+kj!Gn,j
因此可以建出Hn,i和i!Gn,i，直接用NTT求卷积即可，需要注意的是，Fn,k对应的是卷积结果的n+k次项系数。
复杂度O(nlogn)。
腾讯稳定性 120人发布
投递中国银行等公司10个岗位 >
