小白月赛E题个人题解

看到数据范围可见n^2必然会超时，那么就不能用暴力的思路处理，我们必须思考以下两个问题。

怎样合理的枚举？

注意到F数组的第n行的贡献为 a[n] 记为 C[n]

第n-1行的贡献为 a[n-1] + a[n-1] * a[n] = a[n-1] * (1 + a[n])

我们发现，从n行往上枚举，设第 i 行的贡献为 C[i] ,则 C[i] = a[i] * (1 + C[i+1])

那么将所有的 C[i] 加起来就是答案， 至此我们可以O(n)的进行枚举

如何处理25的倍数？

对于构成每一行贡献的和式（即C[i]中的加项），有些数是25的倍数，有些不是，我们不能逐一判别。

但我们能通过预处理的办法先把每个 a[i] 变为只是 5 在其中的次幂只是 0 或 1

这启发我们， 是否可以对答案维护两个项 t0 和 t1

分别代表在 i+1 行的贡献中不是 5 的倍数的那些加项的和，以及是5的倍数的加项和

这样在计算C[i] 时只需要维护好 t0 和 t1 即可

考虑维护 t0 和 t1

当 a[i] % 5 !=0 时，没有出现25的倍数，则：

t0 = (t0 + 1) * a[i] , t1 = t1 * a[i]

否则， t1 * a[i] 后是25的倍数， 应该乘25的逆元， t0 * a[i] 后是5的倍数， 在统计答案后交换t0,t1即可

t0 = (t0 + 1) * a[i] , t1 = t1 * a[i] * 逆25, swap(t0,t1)

最后遍历统计答案即可

处理部分代码如下

    ll t0=0,t1=0;
    if(a[n]%5==0) t1+=a[n];
    else t0+=a[n];
    
    ll res=a[n];
    ll mul=quipow(25,M-2,M);
    for(int i=n-1;i>=1;--i)
    {
        t0=(t0+1)*a[i]%M,t1=t1*a[i]%M;//1加在t0 , 因为 1 不是5的倍数
        if(a[i]%5==0) 
        {
            t1=t1*mul%M;
            res=(res+t0+t1)%M;
            swap(t0,t1);
        }
        else res=(res+t0+t1)%M;
    }

题外话，赛时把mul = quipow(25,M-2,M)写成 mul = (25,M-2,M) 一小时没看出来，还是太菜了

最后，第一次写题解，难免有疏漏或是表达失当，欢迎指正，希望对你有所帮助。