ABC288F前缀和相邻项乘法分配律优化DP

给定一个n位数X，把X分成若干段，得分为每一段的乘积。求所有分法得分之和模998244353。

f[i]表示前i位的乘积之和，前驱为少一段数字，枚举这段数字的长度即可得到n方做法：

#include <stdio.h>
const int N=200050, mo=998244353;
int n, m, i, j, k;
char c[N];
long long a[N], s[N], f[N];
int cal(int x, int y){
    return (s[y]-s[x]*a[y-x]) % mo + mo;
}
int main(){
    scanf("%d%s", &n, c+1);
    for(a[0]=i=1; i<=n; i++){
        s[i] = (s[i-1]*10 + c[i]-48) % mo;
        a[i] = a[i-1] * 10 % mo;
    }
    for(f[0]=i=1; i<=n; i++){
        for(j=1; j<=i; j++){
            f[i] += f[i-j] * cal(i-j, i) % mo;
        }
    }
    printf("%lld\n", f[n]%mo);
    return 0;
}

好像不能简单地用前缀和优化掉循环，那就找一下相邻两项的关系：
f[i] = 1 f[i-1] + 21 f[i-2] + 321 f[i-3] ...
f[i-1] = 2 f[i-2] + 32 f[i-3] ...
f[i]将最右边那一位“1”提取出来，剩下的就是f[i-1] 10了！只需要再加上最后一位乘以f的前缀和即可。

#include <stdio.h>
const int N=200050, mo=998244353;
int n, m, i, j, k;
char c[N];
long long f[N], s;
int main(){
    scanf("%d%s", &n, c+1);
    for(s=i=1; i<=n; i++){
        f[i] = (f[i-1]*10 + (c[i]-48)*s) % mo;
        s += f[i];
    }//s赋初值为1，即可考虑到不断开的情况
    printf("%lld\n", f[n]%mo);
    return 0;
}