This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |