E - Digit Circus思路看到这道题10的500次方的数据范围以及对于每一位数字、数字和和数字种类的讨论我们不难想到这是一道数位DP。那现在的问题就是怎么去完成数位DP的过程。首先我们的DP必须要考虑到题目要求的所有目标3的倍数、含有3、用到3种不同的数字。同时我们也要记录数位DP通用的状态考虑到第几位、是否触及上限。于是我们可以得到一个DP数组dp[i][j][op][mask] i 表示考虑到从左到右的第 i 位j 表示当前余数为 j op 表示当前是否含有 3 mask 是一个对于用到哪些数字的状态压缩。考虑到这道题目要求仅仅为满足其一数组存储的是有8个元素的容器通过状态压缩表示满足当前条件的数字数量。最后在处理 DP 的过程上我使用了记忆化搜索。正解#includebits/stdc.h #define int long long #define si int using namespace std; typedef vectorint arr; const int N 505; const int mod 998244353; string s; int n; bool vis[N][3][2][110]; arr dp[N][3][2][110]; inline arr dfs(int x, int tight, int mod3, int has3, si mask) { arr res arr(8); if(x n) { int f1 0, f2 0, f3 0; if(mask 0) return res; if(mod3 0) f1 1; if(has3 1) f2 1; if(__builtin_popcount(mask) 3) f3 1; int t f1 | (f2 1) | (f3 2); res[t] 1; return res; } if(!tight vis[x][mod3][has3][mask]) return dp[x][mod3][has3][mask]; int up (tight? s[x] - 0 : 9); for(int d 0; d up; d) { int ntight tight; int nmod3 mod3; int nhas3 has3; si nmask mask; ntight tight (d up); if(mask 0) { if(d ! 0) { nmod3 d % 3; nhas3 (d 3); nmask (1 d); } } else { nmod3 (mod3 * 10 d) % 3; nhas3 has3 | (d 3); nmask mask | (1 d); } auto nxt dfs(x 1, ntight, nmod3, nhas3, nmask); for(int i 0; i 8; i) res[i] (res[i] nxt[i]) % mod; } if(!tight){ vis[x][mod3][has3][mask] true; dp[x][mod3][has3][mask] res; } return res; } signed main() { cins; n s.size(); arr res dfs(0,1,0,0,0); int ans 0; for(si i 0; i 8; i) if(__builtin_popcount(i) 1) ans (ans res[i]) % mod; coutans; return 0; }