526互联

AtCoder Beginner Contest 245 Ex Product Modulo 2

发布时间 2023-06-26 12:52:18作者: zltzlt

洛谷传送门

AtCoder 传送门

很好的题。

下文令 \(k\) 为原题面中的 \(n\)，\(n\) 为原题面中的 \(k\)，\(m\) 为原题面中的 \(m\)。

从一些简单的情况入手。

1. \(m\) 为质数

  • \(k = 0\) 的情况是平凡的，只需要要求 \(\exists i \in [1, n], a_i = 0\) 即可。总方案数减去不合法方案数，答案为 \(m^n - (m - 1)^n\)。
  • \(k \ne 0\) 时，我们发现，\(a_{1 \sim n - 1}\) 可以任取，让 \(a_n\) 取 \(\frac{k}{\prod\limits_{i = 1}^{n - 1} a_i}\)，所以 \(a_{1 \sim n - 1}\) 唯一对应一个 \(a_n\)。因此方案数为 \((m - 1)^{n - 1}\)。

2. \(m = p^e\)，其中 \(p\) 为质数，\(e\) 为正整数

仍然特判掉 \(k = 0\)。设 \(k = r \times p^x\)，其中 \(x < e, \gcd(r, p) = 1\)。我们需要把 \(x\) 个 \(p\) 分配到 \(a_{1 \sim n}\)，方案数为 \(\binom{x + n - 1}{n - 1} = \binom{x + n - 1}{x}\)，然后接下来 \(a_{1 \sim n - 1}\) 都可以任取与 \(p\) 互质的数，同样的它们唯一对应一个 \(a_n\)。因此方案数为 \(\binom{x + n - 1}{x} \times (m - \frac{m}{p})^{n - 1}\)。

3. 一般情况

考虑对 \(m\) 进行质因数分解，设 \(m = p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_c^{e_c}\)。那么我们可以对每个质因数分别处理，根据 CRT 合并答案，也就是乘起来。接下来转化成了 \(2\) 的情况。但是有一点比较尴尬，就是 \(k = r \times p^x\) 中，\(x\) 可能 \(\ge e\)。此时就相当于 \(p_e \mid \prod\limits_{i = 1}^n a_i\)，因此我们可以把任意 \(\ge e\) 个 \(p\) 分配到 \(a_{1 \sim n}\) 中，考虑容斥，总方案数减去分配的 \(p\) 的个数 \(< e\) 的方案数即可。枚举分配 \(p\) 的个数 \(c = [0, e - 1]\)，也转化成了 \(2\) 的情况。但是注意此时的计算中，\(k = r \times p^x\) 中的 \(r\) 是不确定的，因此还要乘上 \(r\) 的方案数。

code 
// Problem: Ex - Product Modulo 2
// Contest: AtCoder - AtCoder Beginner Contest 245
// URL: https://atcoder.jp/contests/abc245/tasks/abc245_h
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;

const ll mod = 998244353;

inline ll qpow(ll b, ll p) {
	b %= mod;
	ll res = 1;
	while (p) {
		if (p & 1) {
			res = res * b % mod;
		}
		b = b * b % mod;
		p >>= 1;
	}
	return res;
}

ll n, m, K;

inline ll C(ll n, ll m) {
	if (n < m || n < 0 || m < 0) {
		return 0;
	} else {
		ll res = 1;
		for (ll i = n; i >= n - m + 1; --i) {
			res = res * i % mod;
		}
		for (ll i = 1; i <= m; ++i) {
			res = res * qpow(i, mod - 2) % mod;
		}
		return res;
	}
}

void solve() {
	scanf("%lld%lld%lld", &n, &K, &m);
	map<ll, ll> mp;
	for (ll i = 2; i * i <= m; ++i) {
		if (m % i == 0) {
			while (m % i == 0) {
				m /= i;
				++mp[i];
			}
		}
	}
	if (m > 1) {
		++mp[m];
	}
	ll ans = 1;
	for (auto p : mp) {
		ll m = 1;
		for (int _ = 0; _ < p.scd; ++_) {
			m *= p.fst;
		}
		ll k = K % m;
		if (k) {
			ll c = 0;
			while (k % p.fst == 0) {
				++c;
				k /= p.fst;
			}
			ll coef = C(c + n - 1, c), t = m - m / p.fst;
			ans = ans * coef % mod * qpow(t, n - 1) % mod;
		} else {
			ll res = qpow(m, n);
			for (int c = 0; c < p.scd; ++c) {
				ll coef = C(c + n - 1, c), t = m - m / p.fst;
				res = (res - coef * qpow(t, n - 1) % mod * (qpow(p.fst, p.scd - c) - qpow(p.fst, p.scd - c - 1) + mod) % mod + mod) % mod;
			}
			ans = ans * res % mod;
		}
	}
	printf("%lld\n", ans);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}