#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define btinpct(x) __builtin_popcountll((x))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?b:gcd(b%a,a); }
#define ll long long int
#define ld long double
#define FOR(ii, ss, ee) for(ll ii = (ss); ii <= (ll)(ee); ++ii)
#define DEC(ii, ss, ee) for(ll ii = (ss); ii >= (ll)(ee); --ii)
typedef pair <ll, ll> pi; typedef pair <ll, pi> spi; typedef pair <pi, pi> dpi;
#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
// #define cerr if(0)cout
#define MAXN (2003)
ll n, cs, cf, mod=1e9+7;
ll dp[MAXN][MAXN];
int main()
{
FAST
cin>>n>>cs>>cf;
if(n<=2) {
cout<<1<<'\n'; return 0;
}
if(cs > cf) swap(cs, cf);
dp[n+1][0]=1;
DEC(i, n, 1) FOR(grps, 0, n-i+1) {
if(i > cf) dp[i][grps] = ((grps?dp[i+1][grps-1]:0) + dp[i+1][grps+1] * (grps+1) % mod * grps % mod) % mod;
else if(i==cf) dp[i][grps] = (dp[i+1][grps] + dp[i+1][grps+1] * (grps+1) % mod) % mod;
else if(i>cs) dp[i][grps] = ((grps?dp[i+1][grps-1]:0) + dp[i+1][grps+1] * (((grps+1) * grps % mod + (grps+1))%mod) % mod) % mod;
else if(i==cs) dp[i][grps] = (dp[i+1][grps] + dp[i+1][grps+1] * (grps+1) % mod) % mod;
else dp[i][grps] = ((grps?dp[i+1][grps-1]:0) + dp[i+1][grps+1] * (((grps+1)*grps%mod+2*(grps+1)%mod)%mod) % mod) % mod;
}
cout<<dp[2][0]<<'\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
504 KB |
Output is correct |
4 |
Correct |
2 ms |
504 KB |
Output is correct |
5 |
Correct |
2 ms |
504 KB |
Output is correct |
6 |
Correct |
2 ms |
504 KB |
Output is correct |
7 |
Correct |
2 ms |
504 KB |
Output is correct |
8 |
Correct |
2 ms |
504 KB |
Output is correct |
9 |
Correct |
2 ms |
504 KB |
Output is correct |
10 |
Correct |
2 ms |
504 KB |
Output is correct |
11 |
Correct |
2 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
504 KB |
Output is correct |
4 |
Correct |
2 ms |
504 KB |
Output is correct |
5 |
Correct |
2 ms |
504 KB |
Output is correct |
6 |
Correct |
2 ms |
504 KB |
Output is correct |
7 |
Correct |
2 ms |
504 KB |
Output is correct |
8 |
Correct |
2 ms |
504 KB |
Output is correct |
9 |
Correct |
2 ms |
504 KB |
Output is correct |
10 |
Correct |
2 ms |
504 KB |
Output is correct |
11 |
Correct |
2 ms |
504 KB |
Output is correct |
12 |
Correct |
4 ms |
1272 KB |
Output is correct |
13 |
Correct |
4 ms |
1272 KB |
Output is correct |
14 |
Correct |
4 ms |
1272 KB |
Output is correct |
15 |
Correct |
4 ms |
1272 KB |
Output is correct |
16 |
Correct |
4 ms |
1272 KB |
Output is correct |
17 |
Correct |
5 ms |
1272 KB |
Output is correct |
18 |
Correct |
4 ms |
1144 KB |
Output is correct |
19 |
Correct |
4 ms |
1272 KB |
Output is correct |
20 |
Correct |
4 ms |
1272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
504 KB |
Output is correct |
4 |
Correct |
2 ms |
504 KB |
Output is correct |
5 |
Correct |
2 ms |
504 KB |
Output is correct |
6 |
Correct |
2 ms |
504 KB |
Output is correct |
7 |
Correct |
2 ms |
504 KB |
Output is correct |
8 |
Correct |
2 ms |
504 KB |
Output is correct |
9 |
Correct |
2 ms |
504 KB |
Output is correct |
10 |
Correct |
2 ms |
504 KB |
Output is correct |
11 |
Correct |
2 ms |
504 KB |
Output is correct |
12 |
Correct |
4 ms |
1272 KB |
Output is correct |
13 |
Correct |
4 ms |
1272 KB |
Output is correct |
14 |
Correct |
4 ms |
1272 KB |
Output is correct |
15 |
Correct |
4 ms |
1272 KB |
Output is correct |
16 |
Correct |
4 ms |
1272 KB |
Output is correct |
17 |
Correct |
5 ms |
1272 KB |
Output is correct |
18 |
Correct |
4 ms |
1144 KB |
Output is correct |
19 |
Correct |
4 ms |
1272 KB |
Output is correct |
20 |
Correct |
4 ms |
1272 KB |
Output is correct |
21 |
Correct |
20 ms |
4728 KB |
Output is correct |
22 |
Correct |
22 ms |
5112 KB |
Output is correct |
23 |
Correct |
24 ms |
5624 KB |
Output is correct |
24 |
Correct |
165 ms |
22988 KB |
Output is correct |
25 |
Correct |
160 ms |
23120 KB |
Output is correct |
26 |
Correct |
168 ms |
23032 KB |
Output is correct |
27 |
Correct |
133 ms |
22904 KB |
Output is correct |
28 |
Correct |
83 ms |
15164 KB |
Output is correct |