solution - CF1422C

littlebug · 2025-04-10 17:07:06 · 题解

补背包 4/48。

但是好像不是背包（）也不知道为啥教练把这道题放到背包题单里……

Solution

首先拆贡献，考虑一个数 a_i（n 从大到小弟 i 位）会产生多少贡献。

那么分两种情况讨论。

• 若删除的区间在 a_i 前面：这时候 a_i 的贡献是不变的，即 a_i \times 10^{n-i}，于是数一下 a_i 前面的情况数即可。
• 若删除的区间在 a_i 后面：假设删除区间的长度为 d，那么 a_i 的贡献就是 a_i \times 10^{n-i-d}，可以发现 d 和区间个数之间是有规律的，d 每 +1，区间个数 -1，于是每个 a_i 所对应的相同 d 的区间个数都是相同的，后缀处理即可。

时间复杂度 O(n)。

Code

int n,a[N],pw10[N];

signed main()
{
    pw10[0]=1; rep(i,1,N-1) pw10[i]=mod_(pw10[i-1]*10);

    string s; read(s),n=s.size();
    rep(i,1,n) a[i]=s[i-1]-'0';

    int ans=0,tmp=0;
    rep(i,1,n) i && add(tmp,i-1),add(ans,mod_(a[i]*tmp*pw10[n-i]));
    tmp=0;
    rpe(i,n,1) i && add(tmp,mod_((n-i)*pw10[n-i-1])),add(ans,mod_(tmp*a[i]));
    write(ans);

    return 0;
}

华风夏韵，洛水天依！