【计数DP】CF1794D

痛定思痛。 2024-02-21 12:04 49阅读 0赞

[Problem - D - Codeforces][]

题意

![06493c1d861a49e6995818c716958851.png][]

思路

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

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

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 <bits/stdc++.h>
    
    #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;
    }

[Problem - D - Codeforces]: https://codeforces.com/contest/1794/problem/D
[06493c1d861a49e6995818c716958851.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/6b11376ece854e45a919c22836cdc813.png