题解 | #Zero#
LCT
https://ac.nowcoder.com/acm/contest/81599/A
DP 太困难了，需要使用脑子。
给出一种不需要使用脑子的做法。复杂度是 +
的。
（为什么加号打不进 latex 里面啊）
我们不妨去统计每个子串的贡献总和。
设 表示区间内问号的个数，
表示区间里
的个数。
我们可以写出这样的一个式子：
我不是很懂为什么所有的加号都被吞了。上面 和
之间应该有一个加号。
式子形式很简单，第一项 可以去掉，我们只需要考虑极长的不包含
的区间即可。
然后你注意到这个东西就是卷积。设 ，那么
使用 NTT 直接做。
