백준 문제 13977번 이항 계수와 쿼리 문제풀이 c++

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

13977번: 이항 계수와 쿼리

 

문제해석

 

 

nCk와 페르마의 소정리 두가지를 동시에 사용하면 이 문제를 풀수가 있다.

 

분자를 A 분모를 B로 p=1000000007로 치환하면

A/B mod p를 구하는 것이 되고 이는 (A mod p * B^-1 mod p) mod p이다.

A mod p는 미리 전처리해주면 그만이고 문제는 B^-1 mod p를 구하는 것인데 여기서 페르마의 소정리를 쓴다.

 

위의 페르마 소정리에서 n^p = n mod p의 양변을 n^2으로 나누면 n^(p-2) = n^-1 mod p 임을 구할수있다.

따라서 B^-1 mod p = B^(p-2) =B^1000000005를 구하면 끝난다.

 

1000000005를 선형으로 곱하면 시간 초과가 나오므로 분할 정복을 통한 거듭제곱을 활용하자

참고로 1000000005를 이진수로 111011100110101100101000000101 이다.

 

 

코드

 

#define MAX 1000000007
#include <iostream>
#include <algorithm>
#include <string>
typedef long long int ll;
using namespace std;
ll ftr[4000001];
string s="111011100110101100101000000101";
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    ftr[0]=1;
    for(int i=1; i<4000001; i++)
    {
        ftr[i]=((i%MAX)*(ftr[i-1]%MAX))%MAX;
    }
    ll m; cin>>m;
    while(m--)
    {
        ll n,k; cin>>n>>k;
        ll A=ftr[n];
        ll base=((ftr[n-k]%MAX)*(ftr[k]%MAX))%MAX;
        ll B=base;
        for(ll i=1; i<s.size(); i++)
        {
            B=((B%MAX)*(B%MAX))%MAX;
            if(s[i]=='1')
            {
                B=((B%MAX)*(base%MAX)%MAX);
            }
        }
        cout<<((A%MAX)*(B%MAX))%MAX<<"\n";
    }
}