E. Falfa with Substring

Solution

考虑容斥，设$G_{n,k}G\_\{n,k\}$表示长度为$nn$的字符串中有至少$kk$个$bitbit$子串的方案数， 则有

那么根据容斥原理，可以推出$F_{n,k}F\_\{n,k\}$和$G_{n,k}G\_\{n,k\}$的关系如下

为了方便起见，将与$jj$无关的项移到左边，得到

令

则化为

因此可以建出$H_{n,i}H\_\{n,i\}$和$i!G_{n,i}i!G\_\{n,i\}$，直接用NTT求卷积即可，需要注意的是，$F_{n,k}F\_\{n,k\}$对应的是卷积结果的$n+kn+k$次项系数。
复杂度$O(n\log n)O(n\backslash log\; n)$。