이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define pb push_back
typedef long long ll;
typedef long double ld;
using namespace std;
#define all(x) (x).begin(), (x).end()
const int mod = (int)1e9 + 7;
const int N = 2001;
void md(int &a){
if(a >= mod)
a-=mod;
}
int binpow(int a , int b){
if(b == 0)return 1;
int ans = binpow(a , b >> 1);
ans = (1ll * ans * ans) % mod;
if(b & 1)
ans = (1ll * ans * a) % mod;
return ans;
}
int INV(int x){
return binpow(x , mod - 2);
}
int dp[2][N];
signed main(){
int n , a , b;
cin >> n >> a >> b;
int bt = 0;
dp[bt][0] = 1;
int inv = 1;
for(int i = 0; i < n - 2; ++i)
inv *= 2;
inv = INV(inv);
int met = 0;
int inv2 = INV(2);
for(int i = n; i >= 1; --i){
/// okay so?
bt ^= 1;
fill(dp[bt] , dp[bt] + N , 0);
if(i == a || i == b){
for(int j = 0; j <= n-i;++j){
/// either add or what
dp[bt][j + 1] += dp[bt^1][j];
md(dp[bt][j + 1]);
int t = j - met;
if(t >= 0){
dp[bt][j] += (1ll * dp[bt^1][j] * t % mod * 2 % mod);
md(dp[bt][j]);
}
if(i == 1){
dp[bt][j - 1] += dp[bt^1][j];
md(dp[bt][j-1]);
}
}
met++;
}else{
for(int j = 0; j <= n-i;++j){
/// either add or what
dp[bt][j + 1] += 1ll * dp[bt^1][j] * inv2 % mod;
md(dp[bt][j + 1]);
int t = j - met;
if(t >= 0){
if(j >= 0)
dp[bt][j - 1] += (1ll * dp[bt^1][j] * t % mod * (t - 1) % mod * 4 % mod), md(dp[bt][j - 1]);
if(j >= 0)
dp[bt][j - 1] += (1ll * dp[bt^1][j] * t % mod * 2 % mod * met % mod), md(dp[bt][j - 1]);
if(i == 1){
dp[bt][j - 1] += dp[bt^1][j];
md(dp[bt][j-1]);
}
}
}
}
// cerr << " after " << i << '\n';
// for(int x = 0; x <= n - i + 1; ++x)
// cerr << dp[bt][x] << ' ';
// cerr << '\n';
}
int ans = dp[bt][1];
cout << ans;
return 0;
}
/*
*/
# | 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... |