计数单位和数位的区别,计数公式excel函数

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 <bits/stdc.h>#define int long longconstexpr 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;}