P11698 [ROIR 2025] 不完全质数 题解
matrixPower
·
·
题解
传送门
声明：
本题我的代码从 kunkunge 的 0 分代码调试而来，使用已经经得他本人同意。
非常好的数位 DP 题。
最近正好学了数位 DP，直接将这一道题拿来练手了。
从题目中可以得知，质数 x 只能拆成 1 \times x，所以不完全质数的各位只能由 1,2,3,5,7 构成，且质数最终只能出现一次。
输入是经典的 l\sim r，由于此题 l 很大，无法快速算出 l-1（除非你想写高精），所以最终表达式是这样：f(r)-f(l)+\operatorname{check(l)}。其中 \operatorname{check(l)} 表示 l 是否为不完全质数，是则答案为 1，不是则答案为 0。
接下来看到 $f(x)$ 如何计算。
考虑到求 $1 \sim x$ 中的个数与 $x$ 非常巨大，可以使用数位 DP 加记忆化。
而我写数位一般使用递归做法。定义递归函数 `dfs`，传 $p,lim,vis,st$ 这四个参数，分别表示现在算到了第 $p$ 位、$lim=1$ 则前面所有位置都顶着上限、$vis=1$ 则表示前面已经用过唯一的指数了，后面只能填 $1$ 了、$st=1$ 表示前面的位置都填的 $0$，即在前导零范围内。
消化了这几个参数后，就可以写题了。
在注意递归边界情况（**严格**按照我的顺序来写）：
1. $vis=1$，则质数已经用过了，后面的位置只能为 $1$。如果此时顶着上线，即 $lim=1$，我们需判断后面所有的位置能否都写下 $1$（比如说 $x=120,lim=1,vis=1$ 就不行）。
2. $p=-1$，由于数位已经用完了还没有用上质数，直接返回 $0$。
3. 如果 $dp_{p,vis} \ne -1$，则说明这次已经查找过了，直接返回这个值即可。
但注意到第一个条件中每次判断时写循环判断是否能全部写下 $1$，每次到这里都要循环，时间复杂度太过巨大，可以开数组 $b$，$b_i$ 表示 $i \sim 0$ 这几位能否存下 $1$。
具体不懂的可以参照代码。
```cpp
#include <bits/stdc++.h>
#define int long long int
using namespace std;
int dp[100005][2],b[100005];
int f[] = {0, 1, 2, 3, 5, 7};
vector<int> num;
int dfs(int p, bool lim, bool vis, bool st)
{
if(vis)
{
if(p==-1) return 1;
return !lim || b[p];
}
if (p == -1) return 0;
if (!lim && ~dp[p][vis] && !st)
return dp[p][vis];
int up = lim ? num[p] : 9;
int ans = 0;
for (auto i : f)
{
if (i > up || (vis && i > 1)) break;
if (st && !i)
{
ans += dfs(p - 1, (lim && (i == up)), 0, 1);
}
else
{
if (i == 0)
continue;
ans += dfs(p - 1, (lim && (i == up)), i != 1, 0);
}
}
if (!lim && !st)
dp[p][vis] = ans;
return ans;
}
int get(string s)
{
reverse(s.begin(), s.end());
num.clear();
for (auto i : s)
num.push_back(i - '0');
b[0]=(num[0]>=1);
for(int i=1;i<num.size();i++)
{
if(num[i]>=2) b[i]=1;
else if(num[i]==1) b[i]=b[i-1];
else b[i]=0;
}
return dfs(num.size() - 1, 1, 0, 1);
}
int check(string s)
{
int flag = 0;
for (auto i : s)
{
if(i!='1')
{
if(i=='0' || i=='4' || i=='6' || i=='8' || i=='9') return 0;
if(flag) return 0;
flag=1;
}
}
return flag;
}
signed main()
{
// freopen("1.in","r",stdin);
memset(dp, -1, sizeof(dp));
string l, r;
cin >> l >> r;
int sum1=get(r);
int sum2=get(l);
cout << sum1 - sum2 + check(l);
return 0;
}
```