# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
48914 |
2018-05-19T21:52:59 Z |
Benq |
Kangaroo (CEOI16_kangaroo) |
C++14 |
|
2000 ms |
14636 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 2001;
template<int SZ> struct Combo {
ll fac[SZ+1], ifac[SZ+1];
Combo() {
fac[0] = ifac[0] = 1;
FOR(i,1,SZ+1) {
fac[i] = i*fac[i-1] % MOD;
ifac[i] = inv(fac[i]);
}
}
ll po (ll b, ll p) { return !p?1:po(b*b%MOD,p/2)*(p&1?b:1)%MOD; }
ll inv (ll b) { return po(b,MOD-2); }
ll comb(ll a, ll b) {
if (a < b || b < 0 || a < 0) return 0;
ll tmp = fac[a]*ifac[b] % MOD;
tmp = tmp*ifac[a-b] % MOD;
return tmp;
}
};
Combo<MX> Co;
int dp[MX][MX];
int ad(int x, int y) { return (x+y)%MOD; }
int mul(int x, int y) { return (ll)x*y%MOD; }
void gen() {
dp[0][0] = 1;
FOR(i,1,MX) {
if (i % 2 == 1) {
FOR(j,1,i+1) dp[i][j] = ad(dp[i][j-1],dp[i-1][j-1]);
} else {
FORd(j,1,i) dp[i][j] = ad(dp[i][j+1],dp[i-1][j]);
}
}
}
int main() {
gen();
ios_base::sync_with_stdio(0); cin.tie(0);
int N, cs, cf; cin >> N >> cs >> cf;
if (cs > cf) swap(cs,cf);
if (cs == 1) {
cout << dp[N-1][cf-1];
return 0;
}
int a = cs-2, b = cf-cs-1, c = N-cf;
//cout << a << " " << b << " " << c << "\n";
int ans = 0;
F0R(A,a+1) {
int mula = Co.comb(a,A);
F0R(B,b+1) {
int mulb = mul(mula,Co.comb(b,B));
F0R(C,c+1) {
//cout << A << " " << B << " " << C << " " << dp[A+1+B+C][A+1] << " " << dp[a+b+c+1-A-B-C][a+b+1-A-B] << "\n";
ans = ad(ans,mul(mul(dp[A+1+B+C][A+1],dp[a+b+c+1-A-B-C][a+b+1-A-B]),mul(mulb,Co.comb(c,C))));
}
}
// A+1 on left, B+C on right
// a+b+1-A on left, c-C on right
}
cout << ans;
}
// read the question correctly (is y a vowel? what are the exact constraints?)
// look out for SPECIAL CASES (n=1?) and overflow (ll vs int?)
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
14328 KB |
Output is correct |
2 |
Correct |
28 ms |
14328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
14328 KB |
Output is correct |
2 |
Correct |
28 ms |
14328 KB |
Output is correct |
3 |
Correct |
28 ms |
14328 KB |
Output is correct |
4 |
Correct |
28 ms |
14328 KB |
Output is correct |
5 |
Correct |
30 ms |
14356 KB |
Output is correct |
6 |
Correct |
29 ms |
14356 KB |
Output is correct |
7 |
Correct |
30 ms |
14376 KB |
Output is correct |
8 |
Correct |
31 ms |
14492 KB |
Output is correct |
9 |
Correct |
29 ms |
14608 KB |
Output is correct |
10 |
Correct |
28 ms |
14608 KB |
Output is correct |
11 |
Correct |
28 ms |
14608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
14328 KB |
Output is correct |
2 |
Correct |
28 ms |
14328 KB |
Output is correct |
3 |
Correct |
28 ms |
14328 KB |
Output is correct |
4 |
Correct |
28 ms |
14328 KB |
Output is correct |
5 |
Correct |
30 ms |
14356 KB |
Output is correct |
6 |
Correct |
29 ms |
14356 KB |
Output is correct |
7 |
Correct |
30 ms |
14376 KB |
Output is correct |
8 |
Correct |
31 ms |
14492 KB |
Output is correct |
9 |
Correct |
29 ms |
14608 KB |
Output is correct |
10 |
Correct |
28 ms |
14608 KB |
Output is correct |
11 |
Correct |
28 ms |
14608 KB |
Output is correct |
12 |
Correct |
32 ms |
14608 KB |
Output is correct |
13 |
Correct |
31 ms |
14608 KB |
Output is correct |
14 |
Correct |
29 ms |
14608 KB |
Output is correct |
15 |
Correct |
34 ms |
14608 KB |
Output is correct |
16 |
Correct |
30 ms |
14608 KB |
Output is correct |
17 |
Correct |
35 ms |
14608 KB |
Output is correct |
18 |
Correct |
30 ms |
14608 KB |
Output is correct |
19 |
Correct |
32 ms |
14608 KB |
Output is correct |
20 |
Correct |
33 ms |
14608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
14328 KB |
Output is correct |
2 |
Correct |
28 ms |
14328 KB |
Output is correct |
3 |
Correct |
28 ms |
14328 KB |
Output is correct |
4 |
Correct |
28 ms |
14328 KB |
Output is correct |
5 |
Correct |
30 ms |
14356 KB |
Output is correct |
6 |
Correct |
29 ms |
14356 KB |
Output is correct |
7 |
Correct |
30 ms |
14376 KB |
Output is correct |
8 |
Correct |
31 ms |
14492 KB |
Output is correct |
9 |
Correct |
29 ms |
14608 KB |
Output is correct |
10 |
Correct |
28 ms |
14608 KB |
Output is correct |
11 |
Correct |
28 ms |
14608 KB |
Output is correct |
12 |
Correct |
32 ms |
14608 KB |
Output is correct |
13 |
Correct |
31 ms |
14608 KB |
Output is correct |
14 |
Correct |
29 ms |
14608 KB |
Output is correct |
15 |
Correct |
34 ms |
14608 KB |
Output is correct |
16 |
Correct |
30 ms |
14608 KB |
Output is correct |
17 |
Correct |
35 ms |
14608 KB |
Output is correct |
18 |
Correct |
30 ms |
14608 KB |
Output is correct |
19 |
Correct |
32 ms |
14608 KB |
Output is correct |
20 |
Correct |
33 ms |
14608 KB |
Output is correct |
21 |
Correct |
201 ms |
14616 KB |
Output is correct |
22 |
Correct |
230 ms |
14628 KB |
Output is correct |
23 |
Correct |
241 ms |
14636 KB |
Output is correct |
24 |
Execution timed out |
2063 ms |
14636 KB |
Time limit exceeded |
25 |
Halted |
0 ms |
0 KB |
- |