【问题求解I-HW4.C】jyy为什么是神

大家容易想到的一个非常简明的做法是使用三重循环计数：

ans = 0;
for (int i = 0; i < int(s.size()); i++)
    for (int j = i + 1; j < int(s.size()); j++)
        for (int k = j + 1; k < int(s.size()); k++)
            if (s[i] == 'j' && s[j] == 'y' && s[k] == 'y')
                ans++;

但由于此题中 $|s|$ 达到了 $10^6$，使用三重循环意味着循环最内层的核心语句被执行了将近 $|s|^3$ 次。计算机一秒钟可以执行的 C/C++ 基本语句数目大约在 $10^8$ 量级，这样的程序显然会超时。

本题的出题助教 (aka. dxy) 希望大家构造自动机解题。这里我们给出一个另外的比较简单的思路：

我们将上面的程序改写为如下伪代码：

ans = 0;
for (int i = 0; i < int(s.size()); i++)
    if (s[i] == 'j')
        ans += "s[i]的后面(可以不连续)的yy的数目";

之前的代码中我们使用双重循环来数 “yy” 的个数，但事实上我们有更快速的方法：假设 s[i] 的后面一共有 n 个字母y，那么任意挑选两个都可以组成一个yy，所以yy的总数目是 $\binom{n}{2}=\frac{1}{2}n(n-1)$。基于这个想法，我们可以用一个二重循环解决该问题：

ans = 0;
for (int i = 0; i < int(s.size()); i++)
    if (s[i] == 'j')
    {
        int y_count = 0;
        for (int j = i + 1; j < int(s.size()); j++)
            if (s[j] == 'y') y_count++;
        ans += C(y_count, 2); // 组合数需要另外实现
    }

我们的算法已经得到了改进，但 $|s|^2$ 次运行仍然无法在规定时间内获得结果，算法还需要进一步的优化。上述方法的瓶颈在于我们每遇到一个j都会把它后面的y数一遍，这样有很多的字母y被反复数了很多遍，这无疑拖慢了速度。

事实上，一个巧妙的顺序的改变就可以“柳暗花明”：我们将外层循环的顺序倒过来，一边寻找j一边把j“身后”的y的个数数出来，这样就不需要内层循环了：

ans = y_count = 0;
for (int i = int(s.size()) - 1; i >= 0; i--) {
    if (s[i] == 'y') y_count++;
    if (s[i] == 'j') ans += C(y_count, 2);
}

循环的使用方法博大精深，大家可以仔细体会这段代码。

此外，本题由于结果过大，最终需要输出答案对 $998244353$ 取模的结果。大家在本题中可能会使用乘法，此时必须格外小心两个 int 类型变量相乘 (还没来得及取模时) 结果溢出的情况，一个好的解决方案是使用更大的数据类型存储中间结果。