C. Bargain(组合数学+贡献)

Codeforces Round #675 (Div. 2)

题意

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

思路

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

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

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

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

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

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

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

#include<bits/stdc++.h> using namespace std; #define int long long const 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(); } }