【计数DP】CF1794D

Problem - D - Codeforces

题意

思路

解法大方向对了，但是还是不会做，原因是组合数不知道怎么求

首先需要注意到一些东西：

1.底数一定是质数

2.质数个数 < n 一定无解

3.哪些质数作为底数是不确定的

4.n <= 2022

那么我们其实可以把做法大致猜出来

根据第4点，应该是个二维的dp，且状态的设计感觉非常唯一：

设 dp[i][j] 表示前 i 个数，已经选了 j 个数作为底数的方案数

然后就是考虑转移，这种计数类的dp在转移的时候都是考虑多一格会多出多少贡献，贡献一般由组合数求出

问题就是出在这里，我不知道怎么求组合数，一心想着对于指数求可重集排列，但是这么多的指数的个数是很难维护的

其实应该考虑分配，算出组合就行了，不用去考虑排列

设多出来那一格的数为 x， 它的个数为 y

那就是考虑把这 y 个 x 分配到 指数中，指数中还剩余多少个空位呢

前缀已经选了 j 个底数，设前缀的个数和为 sum，那么前缀有 sum - j 个数作为指数

所以还剩下 n - (sum - j) 个位置，也就是说，在 n - (sum - j) 个位置中选 y 个位置，那就是 C(n - (sum - j), y)

如果作为底数也是同样的道理

对 x 作为指数还是底数讨论一下即可

Code：

#include 
 
#define int long long
 
constexpr int N = 1e6 + 10;
constexpr int mod = 998244353;
constexpr int Inf = 0x3f3f3f3f;
 
int n, x;
int len = 0;
int Fac[N];
int inv[N];
int vis[N], prime[N];
 
int qpow(int a, int b) {
	int res = 1;
	while(b) {
		if (b & 1) res = (res * a) % mod;
		a = (a * a) % mod;
		b >>= 1;
	}
	return res;
}
int C(int n, int m) {
	if (n < 0 || m < 0 || n < m) return 0;
	return Fac[n] * inv[m] % mod * inv[n - m] % mod;
}
void Fac_init() {
	Fac[0] = 1;
	for (int i = 1; i < N; i ++) {
		Fac[i] = (Fac[i - 1] * i) % mod;
	}
	inv[N - 1] = qpow(Fac[N - 1], mod - 2);
	for (int i = N - 2; i >= 0; i --) {
		inv[i] = inv[i + 1] * (i + 1) % mod;
	}
}
void P_init(int n) {
	vis[1] = 1;
	for (int i = 2; i <= n; i ++) {
		if (!vis[i]) prime[++len] = i;
		for (int j = 1; i <= n / prime[j]; j ++) {
			vis[i * prime[j]] = 1;
			if (i % prime[j] == 0) break;
		}
	}
}
void solve() {
	std::cin >> n;
 
	std::map<int, int> mp;
	for (int i = 1; i <= 2 * n; i ++) {
		std::cin >> x;
		mp[x] += 1;
	}
 
	int sum = 0;
	std::vector<int> dp(n + 1, 0);
	dp[0] = 1;
	for (auto [x, y] : mp) {
		std::vector<int> ndp(n + 1, 0);
		for (int j = 0; j <= n; j ++) {
			ndp[j] += dp[j] * C(n - (sum - j), y) % mod;
			ndp[j] %= mod;
			if (j >= 1 && !vis[x]) {
				ndp[j] += dp[j - 1] * C(n - (sum - j + 1), y - 1) % mod;
				ndp[j] %= mod;
			}
		}
		dp.swap(ndp);
		sum += y;
		sum %= mod;
	}
	
	std::cout << dp[n] % mod << "\n";
}
signed main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
 
	int t = 1;
	Fac_init();
	P_init(1e6);
	while (t--) {
		solve();
	}
	return 0;
}