제출 #747906

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
747906		Amdadul	캥거루 (CEOI16_kangaroo)	C++17	100 / 100	15 ms	22996 KiB

kangaroo

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>

#define ll long long 
  
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
inline ll gen_random(ll l, ll r) {
    return uniform_int_distribution<ll>(l, r)(rng);
}  

#define test cout<<"Test_Round\n"
#define pb push_back
#define pi pair<int,int>
#define pii pair<ll,ll>
#define all(x) x.begin(),x.end()
#define rsort(x) sort(x.rbegin(),x.rend())
#define fastio  ios_base::sync_with_stdio(false),cin.tie(NULL)
#define ull unsigned long long 
#define db double 
#define pai acos(-1)
#define bitcheck(n,k) ((n&(1ll<<k))>0ll)
#define ff first 
#define ss second
bool primecheck(ll x){for(ll i=2;i*i<=x;i++)if(x%i==0)return 0;return 1;}

template<typename type>
void show(vector<type>&a){
    int N=a.size();
  for(int i=0;i<N;i++){
   cout<<a[i]<<" ";
  }cout<<"\n";
}

int cs=0;
void Case(){
  cout<<"Case "<<++cs<<": ";
}

const ll mod=1e9+7;
const int mxx=2e3+2;



ll dp[mxx][mxx];

void solve(){

   int n,s,e;
   cin>>n>>s>>e;
   
   dp[0][0]=1;

   for(int i=1;i<=n;i++)
   {
                   if(!(i==s||i==e))
                   { 
                               if(i<min(s,e))
                               {for(int j=1;j<=i;j++){
                                        dp[i][j]=(dp[i-1][j-1]*j+dp[i-1][j+1]*(j))%mod;
                               }
                               }
                               else if(i>max(s,e)){
                               
                                       for(int j=1;j<=i;j++){
                                         dp[i][j]=(max(0ll,dp[i-1][j-1]*(j-2))+dp[i-1][j+1]*(j))%mod;
                                       }
                               }
                               else if(i>s){
                                       for(int j=1;j<=i;j++){
                                         dp[i][j]=(dp[i-1][j-1]*(j-1)+dp[i-1][j+1]*(j))%mod;
                                       }
                               }
                               else{
                                       for(int j=1;j<=i;j++){
                                         dp[i][j]=(dp[i-1][j-1]*(j-1)+dp[i-1][j+1]*(j))%mod;
                                       }
                               }
                   }
                   else if(i==s){
                               
                               for(int j=1;j<=i;j++){
                                       dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%mod;
                               }
                   }
                   else{
                              for(int j=1;j<=i;j++){
                                       dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%mod;
                                      
                               }

                   }
   }
   cout<<dp[n][1]<<"\n";
}



int main(){
     fastio;
    // freopen("input.txt", "r", stdin);      
    // freopen("output.txt", "w", stdout);
     int t=1;//cin>>t;
     while(t--){
      solve();
     }
}

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