#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = 202;
const int MOD = (int)1e9 + 7;
int dp[N][N][N][2];
void add(int &a, int b){
a += b;
if(a >= MOD) a -= MOD;
}
int main(){
fastIO;
int n, a, b;
cin >> n >> a >> b;
a -- ;
b -- ;
dp[2][0][1][1]=1;
dp[2][1][0][0]=1;
for(int len = 3; len <= n; len ++ ){
for(int x = 0; x < len; x ++ ){
for(int y = 0; y < len; y ++ ){
if(x == y) continue;
// compute q = 1
for(int nx = 0; nx < x; nx ++ ){
add(dp[len][x][y][0],dp[len-1][nx][y-(y>x)][1]);
}
for(int nx = x + 1; nx < len; nx ++ ){
add(dp[len][x][y][1],dp[len-1][nx-1][y-(y>x)][0]);
}
}
}
}
cout << (dp[n][a][b][0] + dp[n][a][b][1]) % MOD;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
1004 KB |
Output is correct |
4 |
Correct |
4 ms |
1772 KB |
Output is correct |
5 |
Correct |
4 ms |
1644 KB |
Output is correct |
6 |
Correct |
4 ms |
1772 KB |
Output is correct |
7 |
Correct |
3 ms |
1516 KB |
Output is correct |
8 |
Correct |
4 ms |
1644 KB |
Output is correct |
9 |
Correct |
4 ms |
1772 KB |
Output is correct |
10 |
Correct |
5 ms |
1772 KB |
Output is correct |
11 |
Correct |
4 ms |
1644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
1004 KB |
Output is correct |
4 |
Correct |
4 ms |
1772 KB |
Output is correct |
5 |
Correct |
4 ms |
1644 KB |
Output is correct |
6 |
Correct |
4 ms |
1772 KB |
Output is correct |
7 |
Correct |
3 ms |
1516 KB |
Output is correct |
8 |
Correct |
4 ms |
1644 KB |
Output is correct |
9 |
Correct |
4 ms |
1772 KB |
Output is correct |
10 |
Correct |
5 ms |
1772 KB |
Output is correct |
11 |
Correct |
4 ms |
1644 KB |
Output is correct |
12 |
Correct |
1652 ms |
32664 KB |
Output is correct |
13 |
Correct |
1309 ms |
29004 KB |
Output is correct |
14 |
Correct |
1669 ms |
32636 KB |
Output is correct |
15 |
Correct |
1674 ms |
32852 KB |
Output is correct |
16 |
Correct |
1661 ms |
32636 KB |
Output is correct |
17 |
Correct |
1665 ms |
33008 KB |
Output is correct |
18 |
Correct |
1065 ms |
26340 KB |
Output is correct |
19 |
Correct |
1591 ms |
31904 KB |
Output is correct |
20 |
Correct |
1662 ms |
32952 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
1004 KB |
Output is correct |
4 |
Correct |
4 ms |
1772 KB |
Output is correct |
5 |
Correct |
4 ms |
1644 KB |
Output is correct |
6 |
Correct |
4 ms |
1772 KB |
Output is correct |
7 |
Correct |
3 ms |
1516 KB |
Output is correct |
8 |
Correct |
4 ms |
1644 KB |
Output is correct |
9 |
Correct |
4 ms |
1772 KB |
Output is correct |
10 |
Correct |
5 ms |
1772 KB |
Output is correct |
11 |
Correct |
4 ms |
1644 KB |
Output is correct |
12 |
Correct |
1652 ms |
32664 KB |
Output is correct |
13 |
Correct |
1309 ms |
29004 KB |
Output is correct |
14 |
Correct |
1669 ms |
32636 KB |
Output is correct |
15 |
Correct |
1674 ms |
32852 KB |
Output is correct |
16 |
Correct |
1661 ms |
32636 KB |
Output is correct |
17 |
Correct |
1665 ms |
33008 KB |
Output is correct |
18 |
Correct |
1065 ms |
26340 KB |
Output is correct |
19 |
Correct |
1591 ms |
31904 KB |
Output is correct |
20 |
Correct |
1662 ms |
32952 KB |
Output is correct |
21 |
Runtime error |
1790 ms |
67680 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
22 |
Halted |
0 ms |
0 KB |
- |