「学习笔记」数位 DP

目录

• 「学习笔记」数位 DP
  • 概述
  • 例题
    • P2657 [SCOI2009] windy 数
      • 思路
      • 代码
    • P4317 花神的数论题
      • 思路
    • P4124 [CQOI2016]手机号码
      • 思路
      • 代码
    • haha数
      • 题意
      • 思路
      • 代码
    • 0和1的熟练
      • 题意
      • 思路
      • 代码
    • 苍与红的试炼
      • 题意
      • 思路
      • 代码

const ll N = 15, inf = 1ll << 40, P = 1e9 + 7;
namespace SOLVE {
	ll a, b, f[N][N], g[N];
	inline ll rnt () {
		ll x = 0, w = 1; char c = getchar ();
		while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
		while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
		return x * w;
	}

	inline ll GetAns (ll x) {
		ll len = 0, num[N] = {0}, sum = 0;
		while (x) num[++len] = x % 10, x /= 10;
		for_ (i, len, 1) {
			if (i == len) {
				_for (j, 0, num[i] - 1) sum += f[i][j];
				sum += g[i];
				continue;
			}
			_for (j, 0, num[i] - 1) {
				if (abs (j - num[i + 1]) < 2) continue;
				sum += f[i][j];
			}
			if (abs (num[i] - num[i + 1]) < 2) break;
		}
		return sum;
	}

	inline void In () {
		a = rnt (), b = rnt ();
		return;
	}
	inline void Solve () {
		_for (i, 0, 9) f[1][i] = 1;
		g[1] = 2;
		_for (i, 2, 10) {
			g[i] = g[i - 1] + f[i - 1][0] + f[i - 1][1];
			_for (j, 0, 9) {
				_for (k, 0, 9) {
					if (abs (j - k) < 2) continue;
					f[i][j] += f[i - 1][k];
				}
			}
		}
		return;
	}
	inline void Out () {
		printf ("%lld\n", GetAns (b + 1) - GetAns (a));
		return;
	}
}

ll Dfs (ll p, ll a, ll b, ll sm, ll fr, ll et, ll li) {
	if (fr && et) return 0;
	if (!p) return sm;
	if (!li && f[p][a][b][sm][fr][et] > 0) return f[p][a][b][sm][fr][et];
	ll sum = 0, mx = li ? t[p] : 9;
	_for (i, 0, mx) sum += Dfs (p - 1, i, a, sm || (i == a && i == b), fr || (i == 4), et || (i == 8), li && i == mx);
	if (!li) f[p][a][b][sm][fr][et] = sum;
	return sum;
}
inline ll GetAns (ll x) {
	if (x < 1e10) return 0;
	ll len = 0, sum = 0;
	while (x) t[++len] = x % 10, x /= 10;
	memset (f, -1, sizeof (f));
	_for (i, 1, t[len]) sum += Dfs (len - 1, i, 0, 0, i == 4, i == 8, i == t[len]);
	return sum;
}

inline ll w (ll x) { return (x < 2) ? 0 : (1 << (x - 2)); }
inline bool Check (ll md, ll sta) {
	_for (i, 2, 9) if ((sta & w (i)) && (md % i)) return 0;
	return 1;
}

ll Dfs (ll p, ll md, ll sta, ll li) {
	if (!p) return Check (md, sta);
	if (!li && f[p][md][sta] >= 0) return f[p][md][sta];
	ll sum = 0, mx = li ? t[p] : 9;
	_for (i, 0, mx) sum += Dfs (p - 1, (md * 10 + i) % 2520, sta | w (i), li & (i == mx));
	if (!li) f[p][md][sta] = sum;
	return sum;
}

ll Dfs (ll p, ll c1, ll len, ll li) {
	if (!p) return len ? (len - c1 >= c1) : 1;
	if (!li && f[p][c1][len] >= 0) return f[p][c1][len];
	ll sum = 0, mx = li ? t[p] : 1;
	_for (i, 0, mx) sum += Dfs (p - 1, c1 + (i == 1), len + (len || i), li & (i == mx));
	if (!li) f[p][c1][len] = sum;
	return sum;
}

namespace SOLVE {
	const ll N = 1e7;
	ll d, s, f[N], g[N], jl[N], ans;
	inline ll rnt () {
		ll x = 0, w = 1; char c = getchar ();
		while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
		while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
		return x * w;
	}
	void Print (ll p) {
		if (p == 1) return;
		Print (g[p]);
		printf ("%lld", f[p]);
	}
	inline void In () {
		d = rnt (), s = rnt ();
		return;
	}
	inline void Solve () {
		std::queue <ll> q;
		q.push (0);
		jl[0] = 1;
		ll h = 0, t = 1;
		while (!q.empty ()) {
			ll fr = q.front ();
			++h, q.pop ();
			_for (i, 0, 9) {
				ll dd = (fr % 501 * 10 + i) % d;
				ll ss = fr / 501 + i;
				ll num = dd + ss * 501;
				if (ss > s) continue;
				if (jl[num]) continue;
				f[++t] = i, g[t] = h;
				if (!dd && ss == s) {
					ans = t;
					return;
				}
				jl[num] = 1;
				q.push (num);
			}
		}
		return;
	}
	inline void Out () {
		if (ans) Print (ans), puts ("");
		else puts ("-1");
		return;
	}
}