제출 #1000172

#제출 시각아이디문제언어결과실행 시간메모리
1000172Deepesson캥거루 (CEOI16_kangaroo)C++17
100 / 100
40 ms35668 KiB
#include <bits/stdc++.h>
#define MAX 2005
using ll = long long;
ll tab[MAX][MAX];
bool existe[MAX][MAX];
int N,A,B;
ll MOD = 1e9+7;
ll dp(ll C,ll K){
  //      std::cout<<C<<" "<<K<<"\n";
    if(K==N){
        return (C==1);
    }
    ll P = (K>A)+(K>B);

    if(existe[C][K])return tab[C][K];
    existe[C][K]=1;
    if(K==A||K==B){
    //    std::cout<<"yeah\n";
        int permite=0;
        if(K==N-1)permite=1;
        ll aumenta = dp(C,K+1)*(C-P+permite);
        ll cria = dp(C+1,K+1);
        return tab[C][K]=(aumenta+cria)%MOD;
    }else {
        if(K==N-1){
            if(C!=2)return 0;
            return tab[C][K]=dp(C-1,K+1);
        }
        ll une = 0;
        if(C){
            une=dp(C-1,K+1)*(C-P)*(C-1);
        }
        ll cria = dp(C+1,K+1);
        return tab[C][K]=(une+cria)%MOD;
    }
}
int main()
{
    std::cin>>N>>A>>B;--A;--B;
    std::cout<<dp(0,0)<<"\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...