Codeforces Round #675 (Div. 2)C. Bargain(组合数学+贡献)

题意

去掉一段连续的区间后累加

思路

枚举每一位的贡献，假设该位没有被删除。

从左到右第$i$位,长度为$n$

假设删除该位前面连续的区间

$$\frac{1}{2}?(i?1)?i?str[i]?10^{n?i}$$

在前面任取一段连续的区间可能数为$C_i^2$，乘以$str[i]$的贡献

假设删除该位后面连续的区间

删除区间长度为$x$
$$str[i]?\sum _1^{n?i}(n?i?x+1)?10^{n?i?x}$$
通过代换可以转换为
$$str[i]?\sum _0^{n?i?1}(t+1)?10^t$$

#include<bits/stdc++.h>using namespace std;
#define int long longconst int mod=1e9+7;char str[100010];
int f[100010],p10[100010];
int res(int x){
    return x*(x-1)/2%mod;
}void solve(){
    scanf("%s",str+1);int n=strlen(str+1);p10[0]=1;for(int i=1;i<=100005;++i){
    p10[i]=p10[i-1]*10;p10[i]%=mod;}f[0]=1;for(int i=1;i<=100005;++i){
    f[i]=f[i-1]+(i+1)*p10[i];f[i]%=mod;}int ans=0;for(int i=1;i<=n;++i){
    int pre=res(i)*(str[i]-'0')%mod*p10[n-i];int be=(str[i]-'0')*f[n-i-1];ans+=pre+be;ans%=mod;}printf("%lld\n",ans);
}signed main(){
    int t=1;
// scanf("%lld",&t);while(t--){
    solve();}}