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;
const int mod = 1e9 + 7, N = 2e3 + 1;
ifstream fin("kangaroo.in");
ofstream fout("kangaroo.out");
#define cin fin
#define cout fout
struct Mint
{
int val;
Mint(int x = 0)
{
val = x % mod;
}
Mint(long long x)
{
val = x % mod;
}
Mint operator+(Mint oth)
{
return val + oth.val;
}
Mint operator*(Mint oth)
{
return 1LL * val * oth.val;
}
Mint operator-(Mint oth)
{
return val - oth.val + mod;
}
Mint fp(Mint a, long long n){
Mint p = 1;
while(n){
if(n & 1){
p = p * a;
}
a = a * a;
n /= 2;
}
return p;
}
Mint operator/(Mint oth){
Mint invers = fp(oth, mod - 2);
return 1LL * val * invers.val;
}
friend ostream& operator << (ostream& os, const Mint& lol){
os << lol.val;
return os;
}
void operator += (Mint oth){
val = (1LL * val + oth.val) % mod;
}
};
Mint dp[N][N];
int n, x ,y;
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> x >> y;
dp[1][1] = 1;
for(int i = 2; i <= n; i++){
for(int j = 1; j <= n; j++){
if(i == x){
dp[i][j + 1] += dp[i - 1][j];
dp[i][j] += dp[i - 1][j];
}
else if(i == y){
dp[i][j + 1] += dp[i - 1][j];
dp[i][j] += dp[i - 1][j];
}else{
dp[i][j + 1] += dp[i - 1][j] * (j + 1 - (j > x) - (j > y));
dp[i][j - 1] += dp[i - 1][j] * (j - 1);
}
}
}
cout << dp[n][1];
}
# | 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... |