E - Digit Sum Divisible
题意
定义一个正整数
x
x
x 为
g
o
o
d
good
good 当且仅当：
x
x
x 能被它的数位和 **整除**
统计小于等于
N
N
N 的
g
o
o
d
good
good 正整数数量
思路
这道题关键是要观察到在
N
≤
1
0
14
N \leq 10^{14}
N≤1014 的限制下，数位和种类是有限的：最多只有
9
×
log
10
1
0
14
=
9
×
14
=
126
9 \times \log_{10}10^{14} = 9 \times 14 = 126
9×log101014=9×14=126 种。那么我们可以枚举每一种数位和为
m
o
d
mod
mod，看看有多少正整数
x
x
x 可以被它整除，也就是
x
x
x %
m
o
d
=
0
mod = 0
mod=0
很明显这些涉及到数位统计并且还要计数的问题，我们可以使用 数位
D
P
DP
DP来计算。关键是怎么定义
D
P
DP
DP 状态，还有高位如何利用低位的计算结果。
很显然，对于一个固定的数位和
m
o
d
mod
mod ，我们
D
P
DP
DP 的**状态限制**有：
p
o
s
（低
p
o
s
位是全变化位）
pos（低pos位是全变化位）
pos（低pos位是全变化位）、
s
u
m
（高位的已经确定的数位的和）
sum（高位的已经确定的数位的和）
sum（高位的已经确定的数位的和）、
r
（高位的已经确定的数位单独构成一个数字时模除
m
o
d
的余数）
r（高位的已经确定的数位单独构成一个数字时模除 mod 的余数）
r（高位的已经确定的数位单独构成一个数字时模除mod的余数）
例如：
p
o
s
=
2
,
s
u
m
=
6
,
r
=
3
,
m
o
d
=
20
pos = 2, sum = 6, r = 3, mod = 20
pos=2,sum=6,r=3,mod=20 时，代表的是
12
3
′
0
0
′
→
12
3
′
9
9
′
123 '00' \rightarrow 123 '99'
123′00′→123′99′ 这些数字。因为这些数字的低
p
o
s
=
2
pos = 2
pos=2 位是全变化位，也就是从
0
0
0 ~
9
9
9 任意取的位；更高的位的数位和为
1
+
2
+
3
=
6
=
s
u
m
1 + 2 + 3 = 6 = sum
1+2+3=6=sum；高位已经确定的位单独构成数字
123
123
123 时，模除
m
o
d
=
20
mod = 20
mod=20 的余数是
r
=
3
r = 3
r=3。（当然，这里只是举一个例子，在上述限制条件下，可能还有别的数字符合条件但没有列举出来）
有了限制条件，现在我们考虑如何转移。
根据上述限制我们有定义：
d
p
[
p
o
s
]
[
s
u
m
]
[
r
]
dp[pos][sum][r]
dp[pos][sum][r] 为限制条件下
g
o
o
d
good
good 的正整数数量。如果
N
N
N 的长度为
l
e
n
len
len，那么我们当前的状态下：
p
l
e
n
p
l
e
n
−
1
p
l
e
n
−
2
.
.
.
p
p
o
s
+
1
p
p
o
s
p
p
o
s
−
1
.
.
.
p
2
p
1
p_{len}p_{len-1}p_{len-2} ...p_{pos+1}p_{pos}p_{pos-1}...p_2p_1
plenplen−1plen−2...ppos+1pposppos−1...p2p1，有：
s u m = p l e n + p l e n − 1 + . . . + p p o s + 1 sum = p_{len} + p_{len-1} + ... + p_{pos+1} sum=plen+plen−1+...+ppos+1r = ( 1 0 l e n − 1 ⋅ p l e n + 1 0 l e n − 2 ⋅ p l e n − 1 + . . . + 1 0 p o s ⋅ p p o s + 1 ) r = (10^{len-1} \cdot p_{len} + 10^{len-2} \cdot p_{len-1} + ... + 10^{pos} \cdot p_{pos+1}) r=(10len−1⋅plen+10len−2⋅plen−1+...+10pos⋅ppos+1) % m o d mod mod
那么如果我们枚举当前第
p
o
s
pos
pos 位为
i
i
i 的话，新的状态：
s
u
m
′
=
s
u
m
+
i
sum\prime= sum + i
sum′=sum+i
r
′
=
(
10
×
r
+
i
)
r\prime = (10 \times r + i)
r′=(10×r+i) %
m
o
d
mod
mod
这里关键是观察到
r
′
r\prime
r′ 的变化，通过前面更高位左移（整体
×
10
\times 10
×10 ）得到。
这样我们就完成了状态转移，记忆化搜索到最底层的时候，判断
s
u
m
=
m
o
d
sum = mod
sum=mod 并且
r
=
0
r = 0
r=0 时才返回
1
1
1
时间复杂度：共有
D
=
9
×
14
=
126
D = 9 \times 14 = 126
D=9×14=126 种数位和，范围
N
N
N 长度为
l
e
n
len
len ，每种数位和要搜索的范围可以通过
D
P
DP
DP 数组得出，大约为
l
e
n
×
D
×
m
o
d
len \times D \times mod
len×D×mod
故最终复杂度
O
(
D
3
⋅
l
e
n
)
O(D^3 \cdot len)
O(D3⋅len)
#include<bits/stdc++.h>#definefore(i,l,r)for(int i=(int)(l);i<(int)(r);++i)#definefifirst#definesesecond#defineendl'\n'#defineullunsignedlonglong#defineALL(v) v.begin(), v.end()#defineDebug(x, ed) std::cerr << #x <<" = "<< x << ed;constint INF=0x3f3f3f3e;constlonglong INFLL=1e18;typedeflonglong ll;
ll dp[17][150][150];//dp[pos][sum][r] 表示低pos位为全变化位，前面高位已经确定的数位和为sum，高位模mod为r的数量int num[17];int mod;
ll dfs(int pos,int sum,int r,bool limit){if(!pos)return!r && sum == mod;//最底层，这时候数位和一定要是mod，并且sum % mod 要为 0if(!limit &&~dp[pos][sum][r])return dp[pos][sum][r];
ll res =0;int up =(limit ? num[pos]:9);fore(i,0, up +1){
res +=dfs(pos -1, sum + i,(r *10+ i)% mod, limit && i == up);}if(!limit) dp[pos][sum][r]= res;return res;}
ll solve(ll x){int len =0;while(x){
num[++len]= x %10;
x /=10;}
ll ans =0;for(mod =1; mod <130;++mod){// 枚举整个数位和memset(dp,-1,sizeof(dp));
ans +=dfs(len,0,0,true);}return ans;}intmain(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
ll n;
std::cin >> n;
std::cout<<solve(n);return0;}
本文转载自: https://blog.csdn.net/m0_73500785/article/details/135654850
版权归原作者 吵闹的人群保持笑容多冷静 所有， 如有侵权，请联系我们删除。
版权归原作者 吵闹的人群保持笑容多冷静 所有， 如有侵权，请联系我们删除。