solution

补背包

4/48

。

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

首先拆贡献，考虑一个数

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

CPP

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;
}

华风夏韵，洛水天依！

solution - CF1422C

文章操作

Solution

Code

相关推荐

评论

solution - CF1422C