Codeforces Gym102452J [ICPC2019 香港站] Junior Mathematician

Description

d(x,i)d\left(x,i\right)xx 在十进制下从低往高数第 ii 位数。
xx 在十进制下共 kk 位,令

f(x)=i=1k1j=i+1kd(x,i)d(x,j)f\left(x\right)=\sum_{i=1}^{k-1}\sum_{j=i+1}^kd\left(x,i\right)d\left(x,j\right)

给定 L,R,mL,R,m (10LR<105×103, 2m60)\left(10\leq L\leq R<10^{5\times10^3},\ 2\leq m\leq60\right) ,求

ans=(x=LR[xf(x)(modm)])mod(109+7)ans=\left(\sum_{x=L}^R\left[x\equiv f\left(x\right)\pmod m\right]\right)\bmod{\left(10^9+7\right)}

TT 组测试,保证 log10R5×103\sum\left\lfloor\log_{10}R\right\rfloor\leq5\times10^3 .


Solution

容易想到将 ansans 表示为 前缀和之差 ,记

sumi=x=0i[xf(x)(modm)]sum_i=\sum_{x=0}^i\left[x\equiv f\left(x\right)\pmod m\right]

ans=sumRsumL1ans=sum_R-sum_{L-1}

问题转化为给定 XXsumXsum_X ,考虑 数位 DP .
设某个数 xx 在十进制下共 kk 位,假定当前位为从低往高数第 ii 位。
考虑从低位转移到高位,维护 xxf(x)f\left(x\right) 需要以下信息

si=j=i+1kd(x,j)s_i=\sum_{j=i+1}^kd(x,j)

xi=j=i+1kd(x,j)10j1x_i=\sum_{j=i+1}^kd(x,j)\cdot10^{j-1}

fi=a=i+1k1b=a+1kd(x,a)d(x,b)f_i=\sum_{a=i+1}^{k-1}\sum_{b=a+1}^kd(x,a)d(x,b)

li=[ki=j=i+1k[d(x,j)=d(X,j)]]l_i=\left[k-i=\sum_{j=i+1}^k\left[d\left(x,j\right)=d\left(X,j\right)\right]\right]

显然这样设计状态过多,考虑化简。
注意到

xf(x)(modm)    xf(x)0(modm)x\equiv f\left(x\right)\pmod m\iff x-f\left(x\right)\equiv0\pmod m

因此只需维护 xf(x)x-f\left(x\right) ,即只需知道 di=xifid_i=x_i-f_i 而不需要知道 xi,fix_i,f_i .
dpcur,sum,dta,limdp_{cur,sum,dta,lim} 表示当前考虑到第 curcur 位且 scur=sum, dcur=dta, lcur=lims_{cur}=sum,\ d_{cur}=dta,\ l_{cur}=lim 时对 ansans 的贡献。
设第 curcur 位所填数为 bitbit ,并记

bit=(sum+bit)modmbit'=\left(sum+bit\right)\bmod m

dta=(dta+bit(10cur1sum))modmdta'=\left(dta+bit\left(10^{cur-1}-sum\right)\right)\bmod m

maxbit=d(X,cur)lim+9limmaxbit=d\left(X,cur\right)lim+9\overline{lim}

lim=lim[bit=d(X,cur)]lim'=lim\left[bit=d\left(X,cur\right)\right]

有状态转移方程

dpcur,sum,dta,lim=bit=0maxbitdpcur1,bit,dta,limdp_{cur,sum,dta,lim}=\sum_{bit=0}^{maxbit}dp_{cur-1,bit',dta',lim'}

边界条件 dp0,sum,dta,lim=[dta=0]dp_{0,sum,dta,lim}=\left[dta=0\right] .
注意 卡常 ,应减少 取模次数

时间复杂度:O((log10Rm2))\mathcal O\left(\sum\left(\left\lfloor\log_{10}R\right\rfloor m^2\right)\right) .


Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
inline int add(int a, int b) {
int ret = a + b; return ret < mod ? ret : ret - mod;
}

inline int sub(int a, int b) {
int ret = a - b; return ret < 0 ? ret + mod : ret;
}

const int N = 5e3 + 5;
char L[N], R[N];
int m, base[N];
int bit[N], dp[N][60][60];
int dfs(int cur, int sum, int dta, bool lim) {
if (!cur) return !dta;
if (!lim && ~dp[cur][sum][dta]) return dp[cur][sum][dta];
int mxbit = lim ? bit[cur] : 9, ret = 0;
for (int i = 0; i <= mxbit; i++) {
int nsum = (sum + i) % m;
int ndta = (dta + i * base[cur - 1] + m - i * sum % m) % m;
ret = add(ret, dfs(cur - 1, nsum, ndta, lim && i == mxbit));
}
return lim ? ret : dp[cur][sum][dta] = ret;
}

int get(int len, const char *str) {
for (int i = 1; i <= len; i++)
bit[i] = str[len - i + 1] - '0', memset(dp[i], -1, sizeof dp[i]);
return dfs(len, 0, 0, true);
}

void solve() {
scanf("%s %s %d", L + 1, R + 1, &m);
base[0] = 1; int lenR = strlen(R + 1);
for (int i = 1; i <= lenR; i++) base[i] = base[i - 1] * 10 % m;
int lenL = strlen(L + 1); L[lenL]--;
for (int i = lenL; i && L[i] < '0'; i--) L[i] = '9', L[i - 1]--;
printf("%d\n", sub(get(lenR, R), get(lenL, L)));
}

int main() {
int T; scanf("%d", &T);
while (T--) solve();
return 0;
}

Tsukkomi

前段时间真的忙疯了,期末考、多校、大创 还有游戏 等等一堆破事要搞 orz
一段时间没更博,人菜了,码风变了,省赛打完了 qaq
虽然只是省赛,但热身赛拿了 一血 正赛拿了 Rank 5 还是挺开心的吧 qwq
学弟学妹们一个比一个猛,而我还有几个月就要退役了,一时间不知道该作何感想。

让我们,再一次。最后一次。

Welcome to my other publishing channels