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


백준 15718 돌아온 떡파이어 문제입니다.


문제를 해결하기 위해 1040 이하의 nCr 값을 모두 저장한 후 루카스 정리와 중국인의 나머지 정리를 이용하여 아래와 같이 구현하였으나, WA를 받았습니다.

반례를 찾고 싶은데 찾지 못하여 질문드립니다. 어떤 부분에서 놓친 게 있을까요?


(소스코드)

--------------------------------------------------

#include <stdio.h>


using namespace std;

typedef long long int ll;

ll DP1[1050][1050],DP2[1050][1050],T,N,M,p1,p2;

void comb(){

    DP1[0][0]=1;DP2[0][0]=1;

    for(int i=1;i<=1040;i++){

        for(int j=0;j<=i;j++){

            if(j==0){

                DP1[i][j]=1;DP2[i][j]=1;

                continue;

            }

            DP1[i][j]=(DP1[i-1][j-1]+DP1[i-1][j])%p1;

            DP2[i][j]=(DP2[i-1][j-1]+DP2[i-1][j])%p2;

        }

    }

}

ll power(ll a,ll b,ll p){

    a=a%p;b=b%(p-1);

    if(a==0)return 0;

    ll ans=1;

    while(b>0){

        if(b%2==1)ans=(ans*a)%p;

        b/=2;

        a=(a*a)%p;

    }

    return ans;

}

ll inv(ll a,ll p){ // a != 0

    return power(a,p-2,p);

}

ll lucas1(ll n,ll r,ll p){

    ll ans=1;

    while(n>0){

        ans=(ans*DP1[n%p][r%p])%p;

        n/=p;

        r/=p;

    }

    return ans;

}

ll lucas2(ll n,ll r,ll p){

    ll ans=1;

    while(n>0){

        ans=(ans*DP2[n%p][r%p])%p;

        n/=p;

        r/=p;

    }

    return ans;

}

int main()

{

    p1=97;p2=1031;

    comb();

    scanf("%lld",&T);

    while(T--){

        scanf("%lld%lld",&N,&M);

        if(N==0){

            if(M==1)printf("1\n");

            else printf("0\n");

            continue;

        }

        if(N==1){

            if(M==2)printf("1\n");

            else printf("0\n");

            continue;

        }

        if(M==1){

            printf("0\n");

            continue;

        }

        ll x1=lucas1(N-1,M-2,p1);

        ll x2=lucas2(N-1,M-2,p2);

        ll x=(x1*inv(p2,p1)*p2+x2*inv(p1,p2)*p1)%(p1*p2);

        printf("%lld\n",x);

    }

    return 0;

}

--------------------------------------------------