1 条题解

  • 1
    @ 2024-2-2 16:49:28

    思路:

    对于第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
    上传者