Boj 20296) 폰친구

문제

백준 20296

설명

• 소수로 나누기 때문에 페르마의 소정리 를 사용할 수 있음.
• 조합을 매우 많이 사용하므로 Factorial 값을 전처리 해놓음
• \({}_n C_k = \cfrac{n!}{ k! (n-k)!}\) 에서 전처리한 값을 모듈로 역원을 사용해 조합값을 구함.
• 그리고 중복조합을 사용함.

중복조합의 상한과 하한

\(x+y+z=k\) 이면 \({}_3 H_k = {}_{3+k-1} C_k\) 임

여기에 \(1 \leq x \leq 3, 1 \leq y \leq 3, 1 \leq z \leq 3\) 라면 어떻게 될까.

하한의 경우 미리 하한 값을 준다고 생각해

• \(x+y+z=k-3,\ 0 \leq x \leq 2,\ 0 \leq y \leq 2,\ 0 \leq z \leq 2\) 로 문제를 바꿀 수 있음.

상한은 포함 배제의 원리 를 이용하는게 제일 좋음.

• \(x\), \(y\), \(z\) 각각에 대해서 상한을 초과하는 경우의 수는 하한의 문제로 쉽게 환원할 수 있음. 그러므로 전체에서 이러한 경우의 수를 빼면 됨.
• 예를들어 \(x\) 가 상한을 넘는 경우는 \(x+y+z=k-3-3\) 에 대한 중복조합을 구하면 됨. (2 까지 허용이니 3부터 시작하게 하는 것)
• 이렇게 \(x\), \(y\), \(z\) 에 대해서 구해서 빼면 \((x, y)\) 가 동시에 상한을 넘는 경우가 중복됨. \((x, z)\), \((y, z)\) 도 마찬가지.
• 그러면 \((x, y), (x, z), (y, z)\) 가 상한을 넘는 경우를 구해 더해주고, 또 중복된 경우를 빼주고, 그러다가 중복된 경우가 없을 때까지 반복하면 됨.

시간 복잡도

O(\(\cfrac{K}{M-m} \log{K} +K\))

코드

const int mod = 1e9 + 7;
using ll = long long;

ll ModInv(int t)
{
	int idx = mod - 2; ll base = t, res = 1;
	while (idx)
	{
		if (idx & 1)  res = (res * base) % mod;
		base = (base * base) % mod;
		idx >>= 1;
	}
	return res;
}

ll fact[1005001];
void Init(int n, int k)
{
	fact[0] = 1;
	for (int i = 1; i <= n + k+1; i++)
		fact[i] = fact[i-1] * i % mod;
}

ll C(int n, int k)
{
	return fact[n] * ModInv(fact[n - k]) % mod * ModInv(fact[k]) % mod;
}

// 중복조합
inline ll H(int n, int r)
{
	return C(n + r - 1, r);
}

ll Query(int n, int k, int M, int i=0)
{
	if (k < 0 || i > n) return 0;
	// 상한, 이때 뺄셈이므로 mod 더하는거 잊으면 안됨.
	return (C(n, i) * H(n, k) % mod - Query(n, k - M - 1, M, i+1) + mod) % mod; 
}

int main()
{
	int N, m, M, K;
	cin >> N >> m >> M >> K;

	// 하한
	K -= m * N;
	M -= m;

	Init(N, K);
	cout << Query(N, K, M);
}