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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/159211.html
標籤：其他