题目描述
难度分:$2024$
输入$N(1 \leq N \leq 10^{18})$和$K(1 \leq K \leq 10^9)$。
问:有多少个不超过$N$的正整数,其数位乘积不超过$K$?
输入样例$1$
13 2
输出样例$1$
5
输入样例$2$
100 80
输出样例$2$
99
输入样例$3$
1000000000000000000 1000000000
输出样例$3$
841103275147365677
算法
数位DP
不知道是不是要放假了的原因,灵佬今天选的这道题虽然难度分不低,但是非常“模板”,只要分析清楚状态数量的上界,可以说就是一道数位DP
的板子题。先将$N$转化为字符串$s$,其长度为$n$。
状态定义
$dp[i][mu][islimit][isnum]$表示从数位$i$开始填完最后一个数位$n-1$(数位从高到低用$0$起始标号),能够得到的数位积不超过$K$,且数字大小不超过$N$的数字个数。其中$mu$表示数位$[0,i)$的乘积,$islimit$表示前面的数位是否贴合上界,$isnum$表示前面的数位是否填过数字。
状态转移
$base$ $case$:
很显然,当$i \geq n$时,所有数位就全部填完了,如果$isnum=1$且$mu \leq K$,说明得到了一个符合题意的数字。
一般情况:
如果$isnum=0$,那么当前数位$i$可以继续不填数,状态转移方程为
$dp[i][mu][islimit][isnum]=dp[i+1][mu][0][isnum]$
否则,当前数位尝试填$d \in [1-isnum,ub]$。如果前面的数位$[0,i)$贴合上界,$ub=s[i]$;不贴合上界,则$ub=9$。状态转移方程为
$dp[i][mu][islimit][isnum]=\Sigma_{d=1-isnum}^{ub}dp[i+1][mu \times d][islimit \land digit=d][1]$
复杂度分析
在这个题的数据范围之下,通过打表,发现状态中$mu$的取值最多就是$A=36000$多,因此在最差情况下状态的个数也只有一百多万,而状态转移又是常数级别,因此时间复杂度为$O(An)$($n$就是题干中数字$N$的数位个数)。
空间消耗主要在于状态的存储,和时间复杂度是一个级别的。
C++ 代码
from functools import lru_cache
x, k = map(int, input().split())
s = str(x)
n = len(s)
@lru_cache(None)
def dfs(i: int, mu: int, islimit: int, isnum: int) -> int:
if i >= n:
return 1 if isnum and mu <= k else 0
digit = int(s[i])
cnt = dfs(i + 1, mu, 0, 0) if not isnum else 0
ub = digit if islimit else 9
for d in range(1 - isnum, ub + 1):
cnt += dfs(i + 1, mu*d, islimit and digit == d, 1)
return cnt
res = dfs(0, 1, 1, 0)
dfs.cache_clear()
print(res)