BOJ 7791 - KBTU Party

어느새 백준 800문제를 앞두게 되었다. 790문제인 상태에서 갑자기 800을 특별하게 찍고 싶어서 791~800은 그 숫자가 문제 번호에 포함된 문제들로 풀기로 하였다. 그 시작은 791이 들어있는 7791이다.

문제 태그 : https://www.acmicpc.net/problem/7791

문제 설명 : 1부터 n까지 n명의 여자와 1부터 2n-1번까지 2n-1명의 남자가 있다. 각 여자 i번은 1번~2i-1번까지의 남자들과만 서로 안다. 이때 서로 아는 K쌍을 고를 수 있는 경우의 수를 구하시오.

문제 풀이 : 뭔가 DP보다는 조합식이나 그런것으로 깔끔하게 떨어질 것 같았다. 하지만 큰 경우에 대해서 값을 구하는 과정도 어려웠고, 적은 양의 표본으로는 규칙을 알 수 없어 아예 모든 경우의 수를 구할 수 있는 코드를 짜서 아래와 같은 표를 만들었다. 

이 표를 보니 n, k 에 대해서 경우의 수는 (n!)^2/(n-k)!^2/k! 이라는 것을 알 수 있다. 이때 모듈러를 취해야 하는데, 나누는 경우에는 나누는 대신 잉여역수를 곱해서 해결할 수 있다. 모듈러가 소수이기 때문에 페르마의 소정리에 의해서 j로 나누는 것은 j^(mod-2) 를 곱하는 것과 같다. 

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
ll arr[1010101];
ll mod=2946859;
 
ll lsp(ll a,ll b,ll mod){
    ll ans=1;
    while(b){
        if(b%2) ans=(ans*a)%mod;
        a=(a*a)%mod;
        b/=2;
    }
    return ans;
}
 
int main(){
    ll i,j,k,l,m,n;
    scanf("%lld %lld",&n,&m);
    ll ans=1;
    for(i=1;i<=m;i++){
        ans*=n;
        ans=(ans+mod)%mod;
        ans*=n;
        ans=(ans+mod)%mod;
        ans*=lsp(i,mod-2,mod);
        ans=(ans+mod)%mod;
        n--;
    }
    printf("%lld",ans);
}