DP 太困难了，需要使用脑子。 给出一种不需要使用脑子的做法。复杂度是 + 的。 （为什么加号打不进 latex 里面啊）

我们不妨去统计每个子串的贡献总和。

设 表示区间内问号的个数， 表示区间里 的个数。

我们可以写出这样的一个式子：

我不是很懂为什么所有的加号都被吞了。上面 和 之间应该有一个加号。

式子形式很简单，第一项 可以去掉，我们只需要考虑极长的不包含 的区间即可。

然后你注意到这个东西就是卷积。设 ，那么

使用 NTT 直接做。