Digit Circus
涉及知识点： 数位DP、状态压缩、记忆化搜索
题目描述
请你计算满足以下三个条件中恰好一个的整数 的个数，范围是 ，结果对 998244353 取模。
- 是 3 的倍数。
- 的十进制表示中包含数字 3。
- 的十进制表示中恰好用了三种不同的数字。
注意，整数的十进制表示不允许有多余的前导 0。
约束条件 - 是一个整数。
输入格式
输入 。
输出格式
输出答案。
代码讲解
最大能到 ，普通的遍历必超时，只能用数位 DP。我们在按位枚举填数时，需要维护状态来判断题目给的三个条件。
条件一是判断 3 的倍数，利用特征只需记录当前各数位之和对 3 的余数（rem）。
条件二和三涉及具体出现了哪些数字，用一个二进制状态掩码（mask）来存数字集合最方便。用(mask & (1 << 3)) != 0可以查集合里有没有 3，用__builtin_popcount(mask) == 3能直接拿到集合里不同数字的总数。
逻辑核心是递归函数dfs(pos, rem, mask, isLimit, isHead)。到了递归边界（所有位填完），先把全 0 的情况（isHead仍为真）排除。接着看三个条件命中了几个，恰好 1 个就返回 1，其余返回 0。
填数转移时，前导 0 是不计入数字集合的。处于前导 0 阶段且填入 0 时，mask和rem都不更新。
你提供的代码里有一个经典的记忆化漏洞。你在读取memo时加上了!isLimit && !isHead的限制，但在底部写入memo时直接存了进去。受限状态（比如最高位只能枚举到 4）和前导零状态跑出来的结果，不是通用的排列组合。
正解代码
cpp
#include <bits/stdc++.h>using namespace std;#define int long long#define endl "\n"const int MOD = 998244353;void solve() { string n; cin >> n; int memo[n.size()+1][3][1024]; memset(memo, -1, sizeof(memo)); auto dfs = [&](auto&& dfs, int pos, int rem, int mask, bool isLimit, bool isHead)->int { int r = 0; if (pos == n.size()) { if (isHead) return 0; int a = rem == 0; int b = __builtin_popcount(mask) == 3; int c = (mask & (1 << 3)) != 0; if (a + b + c == 1) return 1; return 0; } if (!isLimit && !isHead && memo[pos][rem][mask] != -1) { return memo[pos][rem][mask]; } int up = (isLimit) ? n[pos]-'0' : 9; for (int i = 0; i <= up; ++i) { int maskNew = mask, remNew = rem; if (!(isHead && i==0)) { maskNew = mask | (1 << i); remNew = (rem + i) % 3; } r = r + dfs(dfs, pos+1, remNew, maskNew, isLimit & (i==up), isHead && (i == 0)) % MOD; r %= MOD; } // 修复：写入记忆化时必须确保状态不受限且无前导零 if (!isLimit && !isHead) { memo[pos][rem][mask] = r; } return r; }; cout << dfs(dfs, 0, 0, 0, 1, 1);}signed main() { ios::sync_with_stdio(false); cin.tie(0); int T = 1; while (T--) { solve(); } return 0;}