讲价 数学问题

题面：



思路：
一开始是想把所有的数字都分解出来，随机组合，后来发现取出的数字是一段连续的数字
然后转变思路：
去看每一位置上的数字能有多少贡献
eg.
a [7][6][5][4][3][2][1][0]
i 7 5 8 3 6 5 8 4
以6为例
（1）
如果是去掉前面一段连续的数字，这个6还是对总的做出的贡献还是a[i]*pow(10,i)
这个算法的重点在于前面去掉一段数的情况有多少种，那么这就涉及到数学问题了
$$1+2+...+(len-i-1)=\frac{(len-i)\cdot (len-i-1)}{2}$$
(2)
如果是去掉后面一部分数字的话，权重（不知道这么叫是不是合适）就会有所改变
以6为例
如果后面去掉1位 a[i]3pow(10,2)
如果后面去掉2位 a[i]2pow(10,1)
如果后面去掉2位 a[i]1pow(10,0)

如果是a[2]=5
如果后面去掉1位 2pow(10,1)
如果后面去掉2位 1pow(10,0)
即后面的这个权重是随着位数的增加有规律地改变的
代码：

#include 
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const ll mod=1e9+7;
ll f[maxn];
string s;
int main()
{
	cin>>s;
	f[0]=1;
	for(int i=1;i<maxn;i++)	f[i]=f[i-1]*10%mod;
	reverse(s.begin(),s.end());
	ll ans=0;
	ll len=s.size();
	ll tmp=0;
	for(int i=0;i<len;i++)
    {
		ll num1=(len-i-1)*(len-i)/2%mod*f[i]*(s[i]-'0')%mod;
		ll num2=(s[i]-'0')*tmp%mod;
		tmp=((i+1)*f[i]%mod+tmp)%mod;
		ans+=(num1+num2)%mod;
		ans%=mod;
	}
	cout<<ans;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27