AtCoder Beginner Contest 465 E - Digit Circus

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 的过程上，我使用了记忆化搜索。

正解

#include<bits/stdc++.h> #define int long long #define si int using namespace std; typedef vector<int> arr; const int N = 505; const int mod = 998244353; string s; int n; bool vis[N][3][2][1<<10]; arr dp[N][3][2][1<<10]; 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() { cin>>s; 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; cout<<ans; return 0; }