1 条题解
-
1
思路:
对于第i位,我们只考虑它本身对于答案的贡献
举个例子:428101984 中的9
1.删除9前面的位数
我们可以发现无论删去9前面的任何数,9对答案的贡献都是不变的,都是900
那我们就考虑,有多少种删除方式即可
可以转换下概念,对于i-1长度的区间删去,一个区间,肯定要有首尾,相当于任取一位当首,在取一位当尾,就应该是(i - 1)*i种
贡献为(i-1)is[i]*p
p是当前位是第几位(10的多少次方)
2.删除他后面的位数
举个例子。
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;
参考代码
for(long long i = n;i >= 1;i--) //n为字符串长度 { long long now = i*(i-1)/2;//删前面有多少种情况 ans = (ans+now*(s[i]-'0')%mod*p%mod)%mod;//删i前面对结果贡献 ans = (ans + sum*(s[i]-'0')%mod)%mod; //删i后面对结果贡献 sum = (sum + (n-i+1)*p%mod)%mod;//删除后面推导的公式模拟 p = p*10%mod;//记录位数 }
- 1
信息
- ID
- 665
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- (无)
- 递交数
- 131
- 已通过
- 22
- 上传者