Submission #745516

#	Time	Username	Problem	Language	Result	Execution time	Memory
745516		_Morningstar	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	21 ms	16060 KiB

kangaroo

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define fr(m) for(int i=0; i<m; i++)
#define fro(m) for(int i=1; i<m; i++)
#define frj(m) for(int j=0; j<m; j++)
#define frr(n) for(int i=n; i>=0; i--)
#define pb push_back
#define pf push_front
#define orr ||
#define nl '\n'
#define nll cout<<'\n'
#define mod 1000000007
#define inf (1LL<<61)
#define inff (1<<30)
#define yes cout<<"YES"<<nl
#define no cout<<"NO"<<nl
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define mxn 2005

template<int MOD>
struct ModInt {
  unsigned x;
  ModInt() : x(0) { }
  ModInt(signed sig) : x((sig>=MOD)?sig%MOD:sig) { }
  ModInt(signed long sig) : x(sig%MOD) { }
  ModInt(signed long long sig) : x(sig%MOD) { }
  int get() const { return (int)x; }
  ModInt pow(ll p) { ModInt res = 1, a = *this; while (p) { if (p & 1) res *= a; a *= a; p >>= 1; } return res; }
 
  ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
  ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
  ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
  ModInt &operator/=(ModInt that) { return (*this) *= that.pow(MOD - 2); }
 
  ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
  ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
  ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
  ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
  bool operator<(ModInt that) const { return x < that.x; }
  friend ostream& operator<<(ostream &os, ModInt a) { os << a.x; return os; }
  friend istream& operator>>(istream &is, ModInt &a) { is >> a.x; return is; }
};
typedef ModInt<mod> mint;//change mod here

int n, st, en;
mint dp[mxn][mxn];

int main()
{
    fastio;
    cin>>n>>st>>en;
    dp[1][1]=1;
    for(int i=2; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(i==st || i==en) dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
            else dp[i][j]=dp[i-1][j+1]*j+dp[i-1][j-1]*(j-(i>st)-(i>en));
        }
    }
    cout<<dp[n][1]<<nl;
    return 0;
}

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