数字之和

题目描述

给定一个数字字符串 n，定义一次操作为：移除字符串中一个非空子串，并将剩余部分拼接形成新数字。

求所有可能操作方案生成的新数字之和，结果对 10⁹+7取模。

输入格式

一行字符串 n

输出格式

一个整数，表示所有方案生成数字之和取模后的结果。

输入样例#1

1003

输出样例#1

339

输入样例#2

123

输出样例#2

52

说明提示

【数据范围】

1≤∣n∣≤10⁵,| n |表示字符串长度。

限制

时间限制：1000ms

内存限制：256MiB

由于数据范围较大，需要利用动态规划的思想来解决这个问题。我们可以定义一个二维数组dp，其中dp[i][j]表示从字符串的第i个字符到第j个字符之间的子串操作生成的所有数字之和。初始时，我们可以设定dp[i][i]为字符串的第i个字符代表的数字。对于dp[i][j]，我们可以根据操作分为两种情况：保留第i个字符和第j个字符之间的子串，或者不保留这个子串。如果保留这个子串，那么dp[i][j]就等于这个子串代表的数字加上dp[i+1][j-1]；如果不保留这个子串，那么dp[i][j]就等于dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]（注意要减去重复计算的部分）。最终的结果就是dp[1][n]，其中n为字符串的长度。为了避免计算过程中的溢出，需要对结果取模。

这个问题可以通过动态规划来解决。我们可以定义一个二维数组dp，其中dp[i][j]表示从字符串的第i个字符到第j个字符之间的子串操作生成的所有数字之和。我们可以根据操作分为两种情况来计算dp[i][j]。对于每一种情况，我们可以递归地计算子问题，直到子问题的规模缩小到只有一个字符。在计算过程中，需要注意避免重复计算，因此需要对结果取模以避免溢出。最终的结果就是dp[1][n]，其中n为字符串的长度。在C语言中，可以利用递归和取模运算来实现这个算法。

以下是C语言的代码实现：

#include <stdio.h>
#include <string.h>
#define MOD 1000000007

long long dp(char *str, int l, int r) {
    if (l == r) {  // 子问题规模缩小到只有一个字符
        return str[l] - '0';  // 返回这个字符代表的数字
    }
    long long res = 0;  // 保存计算结果
    int len = r - l + 1;  // 子串长度
    int mul = pow_mod(10, len - 1);  // 计算乘积避免溢出
    for (int i = l; i <= r; i++) {  // 枚举分割点
        res = (res + dp(str, l, i - 1) * (str[i] - '0') % MOD + dp(str, i + 1, r)) % MOD;  // 计算两种情况的和并取模
    }
    return res * mul % MOD;  // 返回结果并取模
}

int main() {
    char str[100005];  // 存储输入的字符串
    scanf("%s", str);  // 读入字符串
    printf("%lld\n", dp(str, 0, strlen(str) - 1));  // 输出结果
    return 0;
}