C++ 数字计数问题：数字7和5的出现次数

#include\x3cbits/stdc++.h\x3e #define elif else if #define SZ(x) (int)x.size() #define rep(i,a,n) for(int i = (a);i <= (n);i++) #define dec(i,n,a) for(int i = (n);i >= (a);i--) #define inf 0x3f3f3f3f using namespace std; using ll = long long; using PII = pair\x3cint,int\x3e; template\x3cclass T\x3e void print(T x){cout << x << '\n';} template\x3ctypename T\x3e void print(vector\x3cT\x3e &a){for(int i = 0;i < a.size();i ++) cout << a[i] << " \n"[i + 1 == a.size()];} template \x3cclass Head, class... Tail\x3e void print(Head&& head, Tail&&... tail){cout << head << ' '; print(forward\x3cTail\x3e(tail)...);} mt19937 mrand(random_device{}()); int rnd(int x) { return mrand() % x;} const int mod = 1e9 + 7; ll tot, a[20]; ll f[20][20][10], g[20][1 << 7][2]; void get(ll x) { // 取得数字每一位 memset(a, 0, sizeof a); tot = 0; while (x) { a[++tot] = x % 10; x /= 10; } } ll dfs(int pos, int num, bool limit, int cnt) { // cnt 表示数字 num 出现的次数 if (!pos) return cnt; // 如果所有数字都确定直接返回 cnt if (~f[pos][cnt][num] and !limit) return f[pos][cnt][num]; // 如果在不受限下，已经搜过答案，直接返回 int up = limit ? a[pos] : 9; // 判断是否限制解除，如果解除，可选数字设为9 ll ans = 0; for (int i = 0; i <= up; i++) { // 搜索所有子问题 ans += dfs(pos - 1, num, limit && i == up, cnt + (i == num)); // 如果当前数字等于 num，cnt 加 1 } if (!limit) f[pos][cnt][num] = ans; // 如果未受限，更新记忆化表 return ans; } ll dfs2(int pos, int st, bool limit, bool have) { // st 是已经确定的后 7 位是否为 7，have 表示已经确定数字中是否已经有 7 个 7 if (!pos) return have; // 返回是否用用 if (~g[pos][st][have] and !limit) return g[pos][st][have]; ll ans = 0; int up = limit ? a[pos] : 9; for (int i = 0; i <= up; i++) { int nst = ((st & ((1 << 7) - 1 ^ (1 << 6))) << 1) | (i == 7); // 位运算求 next state ans += dfs2(pos - 1, nst, limit && i == up, have || nst == (1 << 7) - 1); } if (!limit) g[pos][st][have] = ans; return ans; } ll solve(ll n) { get(n); ll ans = 3 * dfs(tot, 7, true, 0) + dfs(tot, 5, true, 0); ans += 300 * dfs2(tot, 0, true, false); return ans; }

signed main() { ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); memset(f, -1, sizeof f); // 由于 f，g 都是在未受限情况下定义的，因此可以在多样例中重复使用 memset(g, -1, sizeof g); int T; cin>>T; while(T--) { ll l, r; cin >> l >> r; print(solve(r) - solve(l - 1)); } return 0;