C. Bargain(數學規律+貢獻法列舉優化)詳解

https://codeforces.com/contest/1422/problem/C

---

大晚上算錯資料範圍的我，以為只有50位，直接暴力T5.然後發現是10000位。

貢獻法優化，從低位往高位去列舉，也就是從後往前列舉。比如說列舉到第i位。

考慮第i位前進行連續區間的取。設可以取的整個區間範圍為k.

可以發現，取1長的有k種，取2長的有k-2,取3長的有k-3...可以得出有k*(k+1)/2;

代入長度(i-1)可以得如果在第i位前面去取的話，這個數位的貢獻是i*(i-1)*s[i]*pow[i];

考慮對第i位的後面的進行取。

舉個例子。

8 4 3 2 1

對1來說，後面沒有，那麼貢獻是0

對2來說，後面拿1，貢獻是2

對3來說，後面拿1和2，貢獻是3，後面拿1，貢獻是30，後面拿2，貢獻是30.

對4來說，後面拿123，貢獻是4；後面拿23，21，貢獻是40，40；後面拿3，2，1，貢獻是400，400，400；

歸納起來就是

而後面的這個j*10^(j-1)可以累加更新得到。

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e5+100;
typedef long long LL;
const LL mod=1e9+7;
LL sum[maxn];
char s[maxn];
int main(void)
{
  //cin.tie(0);std::ios::sync_with_stdio(false);
  cin>>(s+1);
  LL len=strlen(s+1);
  LL ans=0;
  LL pw=1;
  LL sum=0;
  for(LL i=len;i>=1;i--)
  {
  	LL num=i*(i-1)/2;
  	ans=(ans%mod+(s[i]-'0')*pw%mod*num%mod)%mod;
  	
	ans=(ans%mod+(s[i]-'0')%mod*sum%mod)%mod;
	
  	sum=(sum%mod+(len-i+1)*pw%mod)%mod;
  	
	pw=pw*10%mod;
  }
  cout<<ans<<endl;
return 0;
}