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+1
- r = ( 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文章来源:https://www.toymoban.com/news/detail-824349.html
时间复杂度:共有
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)文章来源地址https://www.toymoban.com/news/detail-824349.html
#include<bits/stdc++.h>
#define fore(i,l,r) for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;
const int INF=0x3f3f3f3e;
const long long INFLL=1e18;
typedef long long 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 要为 0
if(!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;
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
ll n;
std::cin >> n;
std::cout<< solve(n);
return 0;
}
到了这里,关于AtCoder Beginner Contest 336 E - Digit Sum Divisible的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!