제출 #1361551

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1361551		warrenn	Kangaroo (CEOI16_kangaroo)	C++20	100 / 100	43 ms	55208 KiB

kangaroo

#include<bits/stdc++.h>
using namespace std;
#define int long long 

const int mod=1e9+7;
int dp[2003][2003][3];

void add(int &a,int b){
    a+=b; a%=mod;
}

int mul(int a,int b){
    return (a*b)%mod;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,s,t;
    cin>>n>>s>>t;
    dp[1][1][(s==1) || (t==1)]=1;

    for(int q=1;q<n;q++){
        for(int w=1;w<=q;w++){
            if(q+1==s || q+1==t){
                for(int e=0;e<2;e++){
                    add(dp[q+1][w+1][e+1],dp[q][w][e]); 
                    add(dp[q+1][w][e+1],dp[q][w][e]);
                }
            }
            else{
                for(int e=0;e<3;e++){
                    add(dp[q+1][w+1][e],mul(w+1-e,dp[q][w][e])); 
                    add(dp[q+1][w-1][e],mul(w-1,dp[q][w][e]));
                }
            }
        }
    }
    cout<<dp[n][1][2]<<endl;
}

• 서브태스크 1: 6 / 6
• 서브태스크 2: 30 / 30
• 서브태스크 3: 15 / 15
• 서브태스크 4: 49 / 49