Submission #747612

#TimeUsernameProblemLanguageResultExecution timeMemory
747612Noctambulant캥거루 (CEOI16_kangaroo)C++14
100 / 100
36 ms31644 KiB
// Author:Md. Liad Hossain
// KUET ECE 2K18
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using namespace __gnu_pbds;
#define int long long int
#define nl '\n'
#define ff first
#define ss second
#define pf push_front
#define pb push_back
#define eb emplace_back
#define pof pop_front
#define pob pop_back
#define fbo find_by_order
#define ook order_of_key
#define FOR(i, n) for (int i = 0; i < (int)n; i++)
#define F0R(j, n) for (int j = 1; j <= (int)n; j++)
#define ROF(i, n) for (int i =(int) n - 1; i >= 0; i--)
#define R0F(i, n) for (int i = (int)n; i >= 1; i--)
#define all(v) v.begin(), v.end()
#define lb lower_bound
#define ub upper_bound
#define yes cout << "YES" << nl
#define no cout << "NO" << nl
#define mod 1000000007 //998244353 1000000007
#define setbit __builtin_popcount
#define elif else if
#define mem0(a) memset(a, 0, sizeof(a))
#define mem1(a) memset(a, -1, sizeof(a))
#define inf 9000000000000000000
#define eps 1e-9
// #define pi 2.0 * acos(0.0)
template <class T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
// struct custom_hash {
//   static uint64_t splitmix64(uint64_t x) {
//     x += 0x9e3779b97f4a7c15;
//     x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
//     x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
//     return x ^ (x >> 31);
//   }
//   size_t operator()(uint64_t x) const {
//     static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
//     return splitmix64(x + FIXED_RANDOM);
//   }
// };
 
// knight moves...
// int dx[]={-1,-2,-2,-1,1,2,2,1};
// int dy[]={-2,-1,1,2,2,1,-1,-2};
 
// grid moves without diagonal
// int dx[] = {0, -1, 0, 1};
// int dy[] = {-1, 0, 1, 0};
 
// only all diagonal moves
//  int dx[]={-1,-1,1,1};
//  int dy[]={-1,1,1,-1};
 
// grid moves with diagonal
// int dx[]={0,-1,-1,-1,0,1,1,1};
// int dy[]={-1,-1,0,1,1,1,0,-1};
 
//*************************Code Begins Here*************************//
 
 
 
void solve(){
    int n,a,b;
    cin>>n>>a>>b;
    int dp[n+1][n+1];
    mem0(dp);
    dp[1][1]=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==a || i==b){
                dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%mod;
            }
            else{
                dp[i][j]=((dp[i-1][j-1]*(j-(i>a)-(i>b)))%mod+(dp[i-1][j+1]*j)%mod)%mod;
            }
        }
    }
 
    cout<<dp[n][1]<<nl;
}
 
signed main()
{
    //#ifndef ONLINE_JUDGE
        //freopen("kangaroo.in", "r", stdin);
        //freopen("kangaroo.out", "w", stdout);
    //#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...