题解：P9092 [PA 2020] Liczba Potyczkowa

很愤怒的一道题。

Solution

首先讲一个简单的解法。考虑当

y\ |\ z

时，有

x \bmod y = (x \bmod z) \bmod y

，然后就考虑取

1 \sim 9

的最小公倍数

2520

为初始模数，最后判一下能不能整除包含的数即可（因为没想到这一点而愤怒）。

那就直接状态压缩数位 dp，考虑设

f_{i, 0/1, S, k}

表示，前

i

高位，是否卡着限制，所用数的集合为

S

，且当前数

\text{}\bmod 2520

为

k

的方案数。

转移是显然的。

AC Code

CPP

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp(Tx, Ty) make_pair(Tx, Ty)
#define For(Ti, Ta, Tb) for(auto Ti = (Ta); Ti <= (Tb); Ti++)
#define Dec(Ti, Ta, Tb) for(auto Ti = (Ta); Ti >= (Tb); Ti--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
const int N = 20, M = 2520;
const long long INF = 1e18;
long long L, R;
long long f[2][2][(1 << 9)][2525];
long long work(long long x) {
	if (x == 0) return 0;
	vector<int> num;
	while (x) num.push_back(x % 10), x /= 10;
	reverse(range(num));
	int sz = num.size();
	int flag = 0;
	memset(f, 0, sizeof(f));
	f[0][1][0][0] = 1;
	For(i, 0, sz - 1) {
		memset(f[flag ^ 1], 0, sizeof(f[flag ^ 1]));
		f[flag ^ 1][0][0][0] = 1;
		For(op, 0, 1) {
			For(S, 0, (1 << 9) - 1) {
				For(k, 0, M - 1) {
					if (!f[flag][op][S][k]) continue;
					int lim = (op == 0 ? 9 : num[i] - 1);
					long long val = f[flag][op][S][k];
					For(x, 1, lim) {
						f[flag ^ 1][0][S | (1 << x - 1)][(k * 10 + x) % M] += val;
					}
					if (op && num[i]) {
						int x = num[i];
						f[flag ^ 1][1][S | (1 << x - 1)][(k * 10 + x) % M] += val;
					}
				}
			}
		}
		flag ^= 1;
	}
	long long ans = 0;
	For(S, 1, (1 << 9) - 1) {
		For(k, 0, M - 1) {
			//if (f[flag][0][S][k]) cout << f[flag][0][S][k] << ' ';
			bool g = 1;
			For(j, 1, 9) {
				if (S >> (j - 1) & 1) {
					if (k % j) {
						g = 0;
						break;
					}
				}
			}
			if (g) ans += f[flag][0][S][k] + f[flag][1][S][k];
		}
	}
	return ans;
}
int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	cin >> L >> R;
	if (L == INF) L--;
	if (R == INF) R--;
	long long ans = work(R);
	if (L > 1) ans -= work(L - 1);
	cout << ans;
	return 0;
}

题解：P9092 [PA 2020] Liczba Potyczkowa

文章操作

Solution

相关推荐

评论

题解：P9092 [PA 2020] Liczba Potyczkowa