[BOJ 25917 // C++] Prime Arrangement

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 25917번 문제인 Prime Arrangement이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/25917 

 

먼저, 주어지는 소수들을 임의로 배치했을 때 각 행의 소수들의 곱의 값은 서로 다름을 관찰하자. 주어지는 소수들이 모두 다르므로 소인수분해의 결과가 서로 다를 수밖에 없기 때문이다.

 

따라서 주어진 소수들로 \(R\)개의 행을 구성했을 때, 이 행들을 주어진 가중치 순서대로 나열하는 방법은 유일하게 정해짐을 관찰할 수 있다.

 

따라서 이 문제는 주어진 소수들로 \(R\)개의 행을 구성하는 경우의 수(를 998244353으로 나눈 나머지)를 구하는 것으로 해결할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

ll inv(ll X) {
	ll ret = 1, K = 998244351;
	while (K) {
		if (K & 1) ret = ret * X % 998244353;
		K >>= 1;
		X = X * X % 998244353;
	}
	return ret;
}

ll R, C, RR = 1, RC;
ll ans = 1;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> R >> C;
	RC = R * C;
	for (ll i = 1; i <= RC; i++) ans = (ans * i) % 998244353;
	for (ll i = 1; i <= R; i++) RR = (RR * i) % 998244353;
	RR = inv(RR);
	ans = ans * RR % 998244353;

	cout << ans;
}