自动搬运

查看原文

来自洛谷，原作者为

	_rqy **

搬运于2025-08-24 21:47:17，当前版本为作者最后更新于2017-12-28 08:55:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

注意，本题解当 $L=0$ 的时候可能出错。

看到这题，显然是数位DP。

以下将每个数的“把该数视为一个字符串，列出该字符串的每一个（连续的）子串对应的B进制数的值”简称做该数的权值，记为$q[n]$。

首先要考虑在某个数的后面添加一位数字后，权值会如何改变。

把这个数当成字符串的话，在其后面添加一位，它原来的所有连续子串对其权值的贡献不变，新多出来的权值都是现在的后缀。于是，如果原来的数是$n$，某位添加一个$p$，现在的数是$\overline{np}$，那么有

$q[\overline{np}]=q[n]+\sum_{i=0}^{l[n]} \overline{n[1..i]p}$

其中$l[n]$是$n$的位数，$n[1..i]$是$n$从低到高第$1$到$i$位组成的数（特别的，我们认为$n[1..0]=0$）。

可以发现$\overline{n[1..i]p}=10\times n[1..i]+p$，所以

$q[\overline{np}]=q[n]+\sum_{i=0}^{l[n]} \overline{n[1..i]p}=q[n]+10\sum_{i=1}^{l[n]} n[1..i]+(l+1)q$

令$s[n]=\sum_{i=1}^l n[1..i]$为$n$的后缀和，我们就有$q[\overline{np}]=q[n]+s[\overline{np}]$，同时$s[\overline{np}]=10s[n]+(l[n]+1)q$，$l[\overline{np}]=l[n]+1$。当然，这都是在$n\neq0$的前提下的，否则会出现前导零（也可以认为$l[0]=0$，那样就没有问题了）。

于是我们考虑数位DP时维护$\sum s$，$\sum l$，$\sum q$和数的个数。只要注意不要出现前导零的情况就可以了。

代码中，$a,s,ss,sl$分别表示数的个数、$\sum q$，$\sum s$，$\sum l$。第二维是$0/1$分别表示前$i$位等于/小于原数的时候的值。

代码：

//代码写的丑，不建议分析代码qwq。我自己看着都头疼qwq。
#include <algorithm>
#include <cstdio>
#include <cstring>
typedef long long LL;
const int N = 100050;
const int mod = 20130427;
int n, m, B;
int L[N], R[N];
LL SB[N], S[N];
LL a[N][2], s[N][2], ss[N][2], sl[N][2];
int solve(int *p, int l) {
  memset(a, 0, sizeof a);
  memset(s, 0, sizeof s);
  memset(ss, 0, sizeof ss);
  memset(sl, 0, sizeof sl);
  a[l][0] = 1;
  for (int i = l - 1; ~i; --i) {
    int c = (i == l - 1 ? 0 : B);
    a[i][0] = a[i + 1][0];
    a[i][1] = (c - 1 + a[i + 1][1] * B + a[i + 1][0] * p[i]) % mod;
    sl[i][0] = sl[i + 1][0] + a[i + 1][0];
    sl[i][1] = (c - 1 + sl[i][0] * p[i] +
                (sl[i + 1][1] + a[i + 1][1]) * B) % mod;
    ss[i][0] = (ss[i + 1][0] * B + p[i] * sl[i][0]) % mod;
    ss[i][1] = (S[c] + ss[i + 1][0] * B * p[i] + S[p[i]] * sl[i][0] +
                ss[i + 1][1] * B % mod * B +
                S[B] * (sl[i + 1][1] + a[i + 1][1])) % mod;
    s[i][0] = (s[i + 1][0] + ss[i][0]) % mod;
    s[i][1] = (s[i + 1][0] * p[i] + s[i + 1][1] * B + ss[i][1]) % mod;
  }
  return (s[0][0] + s[0][1]) % mod;
}
int main() {
  scanf("%d", &B);
  SB[0] = 1;
  for (int i = 0; i < N - 1; ++i) SB[i + 1] = (SB[i] * B + 1) % mod;
  S[0] = 0;
  for (int i = 0; i < B; ++i) S[i + 1] = (S[i] + i) % mod;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) scanf("%d", &L[n - i - 1]);
  for (int i = 0; i < n; ++i) {
    if (L[i] > 0) {
      --L[i];
      break;
    }
    L[i] = B - 1;
  }
  if (!L[n - 1]) --n;
  scanf("%d", &m);
  for (int i = 0; i < m; ++i) scanf("%d", &R[m - i - 1]);
  printf("%d\n", (solve(R, m) - solve(L, n) + mod) % mod);
  return 0;
}