[DTCPC 2024] 小方学乘法

Luogu
IDLGP10167
Time1000ms
Memory512MB
DifficultyP6
动态规划 DP2024洛谷月赛拉格朗日插值法
他梦见了一个数学公式,只包含数字和乘号,梦境是迷糊的,所以他可能会把乘号看成字母 $x$。 他冥冥之中记得这个 $x$ 的值,并且他认为字母可以看成数字,因此他在将字母 $x$ 都替换为了数字的情况下算出了这个表达式的值。 然后他被教练抓到睡觉了。 在被 gank 之前,他想回忆起梦中算出的值。 但是小方太困了,所以他决定求出所有情况下的值,也就是将每个**乘号**都替换或者不替换为字母 $x$ 所代表的值后,对所有可能情况求和。 然而小方连 $x$ 都忘记了,只记得它在某个范围 $[L,R]$ 内,所以他要对每个 $x$ 求出上面那个和的和。 小方刚学乘法,算不清太大的数字,所以他想让你求出答案 $\bmod {10^9+7}$ 的结果。 **形式化题意** 给你一个只含有数字 $1 \sim 9$ 和 `?` 的字符串 $s$,保证没有两个相邻的 `?`,且字符串的第一个字符和最后一个字符都不是 `?`。 现在每个 `?` 可以换成 $x$ 或者 $\times$,其中 $x$ 是一个给定的字符串拼接变量。 比如 `12x45` 当 $x=33$ 时替换结果为 `123345`。 记 $x=k$ 时所有 `?` 替换方案下表达式的权值和为 $f(k)$。 求 $\sum_{i=L}^R{f(i)} \bmod {10^9 + 7}$。 ## Input 第一行一个长度为 $n$($1 \le n \le 2000$) 字符串 $S$,表示算式。 第二行两个正整数 $L,R$($1 \le L \le R < 10^{18}$)。 ## Output 一行一个正整数,表示答案对 $10^9+7$ 取模后的结果。 [samples] ## Background 小方上数学课,开始学乘法,但是他在课上睡着了。
Samples
Input #1
123?13?23
1 10
Output #1
507086689
API Response (JSON)
{
  "problem": {
    "name": "[DTCPC 2024] 小方学乘法",
    "description": {
      "content": " 他梦见了一个数学公式,只包含数字和乘号,梦境是迷糊的,所以他可能会把乘号看成字母 $x$。 他冥冥之中记得这个 $x$ 的值,并且他认为字母可以看成数字,因此他在将字母 $x$ 都替换为了数字的情况下算出了这个表达式的值。 然后他被教练抓到睡觉了。 在被 gank 之前,他想回忆起梦中算出的值。 但是小方太困了,所以他决定求出所有情况下的值,也就是将每个**乘号**都替换或者不替换为字母",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10167"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "他梦见了一个数学公式,只包含数字和乘号,梦境是迷糊的,所以他可能会把乘号看成字母 $x$。\n\n他冥冥之中记得这个 $x$ 的值,并且他认为字母可以看成数字,因此他在将字母 $x$ 都替换为了数字的情况下算出了这个表达式的值。\n\n然后他被教练抓到睡觉了。\n\n在被 gank 之前,他想回忆起梦中算出的值。\n\n但是小方太困了,所以他决定求出所有情况下的值,也就是将每个**乘号**都替换或者不替换为字母 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments