제출 #1117797

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1117797		vjudge1	캥거루 (CEOI16_kangaroo)	C++17	0 / 100	1 ms	336 KiB

kangaroo

// #pragma GCC optimize("Ofast,unroll-loops")

// el psy congroo
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert      
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7, sze = 2e3+23, inf = 2e9, LG = 19,pr = 31;
int dp[sze][sze];
void fast(){
    int n,a,b;
    cin>>n>>a>>b;
    dp[1][1]=1;
    for(int i =2;i<=n;i++){
        for(int j=1;j<=i;j++){
            // i,j 
            if( i==a || i==b ){
                dp[i][j] = (dp[i-1][j-1]+ dp[i-1][j] + mod)%mod;
            }
            else{
                if(j!=1){
                    dp[i][j] = (dp[i-1][j] * (i- j) )   %mod;
                }
                dp[i][j] = (dp[i][j] +  dp[i-1][j+1] * (j) + dp[i-1][j-1]*(j - (i>a) - (i>b)) )%mod;
                // cout<<i<<" "<<j<<" :"<<dp[i-1][j]*(i-j)<<" "<<dp[i-1][j+1]*j<<" "<<dp[i-1][j-1]*(j -  (i>a) - (i>b))<<"=> "<<dp[i][j]<<endl;
                /*
                    a _ [] _ [] _ [] _ b 
                        connect 2 : dp[i-1][j+1] * (j)
                        new one :  dp[i-1][j-1] * (j+1 - (i>a) - (i>b))
                        current : dp[i-1][j] * (i  - (i>a) - (i>b));   

                */


            }
            // cout<< i<<" "<<j<<" "<<dp[i][j]<<endl;
        }
    }

    putr( (dp[n][1] + mod )%mod );
}

 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int tt = 1;
    // cin>>tt;
 
    while(tt--){
        fast();
    }
    return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 30
• Subtask 3: 0 / 15
• Subtask 4: 0 / 49