Submission #257580

#	Time	Username	Problem	Language	Result	Execution time	Memory
257580		wzy	Kangaroo (CEOI16_kangaroo)	C++11	100 / 100	61 ms	27128 KiB

kangaroo

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <climits>

using namespace std;

#define F first
#define S second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define all(x) begin(x) , end(x)
#define sz(x) (int)(x).size()
#define pb push_back

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef pair<ll,ll> pll;
typedef vector<string> vs;
typedef vector<pll> vpl;
typedef vector<int> vi;

ll modpow(ll b, ll e ,ll mod){
	ll ans = 1;
	for (; e; b = b * b % mod, e /= 2)
		if (e & 1) ans = ans * b % mod;
	return ans;
}
const int N = 2002;
const int mod = (int) 1e9 + 7;
ll dp[N][N];
bool vis[N][N];
int n , s , t;

ll solve(int x , int y ){
	if(y < 0) return 0;
	if(x == n + 1){
		return (y == 1);
	}
	if(vis[x][y]) return dp[x][y];
	dp[x][y] = 0 , vis[x][y]=  1;
	int ok = y - (x >= s) - (x >= t);
	if(x == s || x == t){
		return dp[x][y] = (solve(x+1,y) + solve(x+1,y+1))%mod;
	}
	dp[x][y] = (dp[x][y] + 1ll * solve(x+1,y+1)*(ok + 1) + 1ll*solve(x+1,y-1)*(y-1)) %mod;
	return dp[x][y];
}



int32_t main(){
	cin >> n >> s >> t;
	cout << solve(1, 0) << endl;
}

/* clever stuff:
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and STAY ORGANIZED
	* Keep it simple stupid
	* WRITE STUFF DOWN
	* math -> gcd / lcm / divisors? 
*/

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