(GT)考试加强版，(n,m)都改为(10^5)，字符集大小（以下称为(k)）改为(10^9)，对(998244353)取模。

(std)给了一个暴力容斥的卷积优化，以及一个用(border)不超过(log)个等差数列的性质的前缀和优化。

不过这里要给出一个神仙做法。

(orz~cx233666!!!)

习惯性的，我们把长度为(n)的串（准考证号）叫做大串，长度为(m)的串（不吉利数字）叫做小串。

设(g_i)表示大串前(i)位不出现小串的概率（以下称为成功），(f_i)表示大串第(i)位恰好第一次出现小串的概率（以下称为失败），那么答案就是(g_i*k^n)。

对于一个成功的方案，下一步可能是成功或失败；对于一个失败的方案，它没法走下一步。所以显然有(g_i=g_{i+1}+f_{i+1})。

然而这个东西看上去好像没啥用啊，别着急，一会有妙用。

接着考虑这样一个问题：对于一个成功的方案，我们让它向后走(m)步，走出一个完整的小串插在后面，思考一下这部分意味着什么。

显然是走向失败了——但由于在走之前我们可能已经走出了小串的前面一部分，最后走上了小串的一个(border)导致提前失败，不过不要忘了我们还是强行让失败的继续走了剩下的步数。最终应当是所有走向失败的方案的总和。

那么就又有一个式子了：

由于(f,g)的定义是概率，所以每一步都要乘上(frac1k)。

接着推上面的式子，把(k)消到右边：

为了让右边看的更优美，并且具有某种性质，我们令(a_{m-i}=[i∈border]k^i)，那么就变成了：

容易发现我们这样做的目的：(a)的下标加上(f)的下标变成了一个定值(i+m)，不绕弯子的说，就是有卷积的形式了。

我们稍微改一下以证明它确实是个卷积：

由于(a)从第(m)项以后全部为(0)，所以上式显然等价于之前的式子。

但正常的来说，应该是(g_{i+m})等于上式才对啊，(g)的下标被搞成了(i)怎么办呢？

很简单，我们写出生成函数：

令(G(x)=sum_ig_ix^i,F(x)=sum_if_ix^i,A(x)=sum_{i=0}^ma_ix^i)

虽然(g_i)的次数不够，但我们可以强行补上：

(x^mG(x)=A*F(x))

由于(F)的前(m)项没有值，所以右边这部分不管怎么卷都是(0)。也就是说，上式虽然左边前(k)项没有值，但右边也没有值，而从(k+1)项开始就满足上面那个式子了，所以不会出什么(bug)。

再看我们最开始写出的式子，用同样的套路，把它用生成函数表示出来：

(xG(x)+1=G(x)+F(x))

注意这次有常数项——后面有(g_0=1)，但你前面乘了个(x)没常数项，所以要补上。

两个式子搞一块整理一下：

求逆在(mod~x^{n+1})意义下进行。

显然(a_0=k^m)，(frac{x^m}{A(x)}+1-x)的常数项为(1)，所以两次求逆都成立。

是不是相当妙啊？

T2

给出一张图，对于任何一个点集，我们把所有能够用点集中的点连出来的边进行计数，求每次计数的(k)次方和，(n,m≤10^5,k≤3)。

几次方就是几条边在同时给答案贡献，那么我们强行分类讨论这几条边由几个点组成，三元环计数即可。

由于时间不够，强行一句话题解。

T3

给出一个字符串，求两个不交（但可以挨在一块）的区间使得它们拼起来是个回文串，求能拼出的最长回文串长度及位置，(n≤5*10^5)。

跑一遍(manacher)，求出所有回文中心的最长长度，假设回文中心在左边，那么问题就变成了从这个极长回文串的左边紧挨着连一个字符串，右边从某个位置选出一个(reverse)后相同的字符串，这个问题就是P4094 [HEOI2016/TJOI2016]字符串。然而我好像不会一个(log)的做法诶~