#include <cstring>
#include <iostream>
//using namespace std;
typedef long long int ll;
int sta, end, n;
ll dp[2010][2010];
static ll MOD = 1000000007;
ll f(int i, int k){
if(k < 0) return 0;
if(i == n - 1) return k == 0;
ll ks = i > sta;
ll ke = i > end;
ll &ret = dp[i][k];
if(ret != -1) return ret;
ret = 0;
if(i == sta || i == end){
ret += f(i + 1, k);
ret += f(i + 1, k - 1)*k;
}
else{
ret += f(i + 1, k + 1);
ret += f(i + 1, k - 1)*k*(k - 1 + ks + ke);
}
return (ret %= MOD);
}
int main(){
std::cin.tie(0);
memset(dp, -1, sizeof dp);
std::ios_base::sync_with_stdio(0);
std::cin >> n >> sta >> end;
--sta, --end;
std::cout << f(0, 0) << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
31864 KB |
Output is correct |
2 |
Correct |
25 ms |
31972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
31864 KB |
Output is correct |
2 |
Correct |
25 ms |
31972 KB |
Output is correct |
3 |
Correct |
24 ms |
32024 KB |
Output is correct |
4 |
Correct |
31 ms |
32212 KB |
Output is correct |
5 |
Correct |
25 ms |
32212 KB |
Output is correct |
6 |
Correct |
33 ms |
32212 KB |
Output is correct |
7 |
Correct |
27 ms |
32236 KB |
Output is correct |
8 |
Correct |
27 ms |
32252 KB |
Output is correct |
9 |
Correct |
32 ms |
32380 KB |
Output is correct |
10 |
Correct |
27 ms |
32380 KB |
Output is correct |
11 |
Correct |
25 ms |
32380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
31864 KB |
Output is correct |
2 |
Correct |
25 ms |
31972 KB |
Output is correct |
3 |
Correct |
24 ms |
32024 KB |
Output is correct |
4 |
Correct |
31 ms |
32212 KB |
Output is correct |
5 |
Correct |
25 ms |
32212 KB |
Output is correct |
6 |
Correct |
33 ms |
32212 KB |
Output is correct |
7 |
Correct |
27 ms |
32236 KB |
Output is correct |
8 |
Correct |
27 ms |
32252 KB |
Output is correct |
9 |
Correct |
32 ms |
32380 KB |
Output is correct |
10 |
Correct |
27 ms |
32380 KB |
Output is correct |
11 |
Correct |
25 ms |
32380 KB |
Output is correct |
12 |
Correct |
27 ms |
32380 KB |
Output is correct |
13 |
Correct |
30 ms |
32380 KB |
Output is correct |
14 |
Correct |
31 ms |
32380 KB |
Output is correct |
15 |
Correct |
26 ms |
32380 KB |
Output is correct |
16 |
Correct |
28 ms |
32380 KB |
Output is correct |
17 |
Correct |
26 ms |
32380 KB |
Output is correct |
18 |
Correct |
26 ms |
32380 KB |
Output is correct |
19 |
Correct |
33 ms |
32380 KB |
Output is correct |
20 |
Correct |
25 ms |
32380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
31864 KB |
Output is correct |
2 |
Correct |
25 ms |
31972 KB |
Output is correct |
3 |
Correct |
24 ms |
32024 KB |
Output is correct |
4 |
Correct |
31 ms |
32212 KB |
Output is correct |
5 |
Correct |
25 ms |
32212 KB |
Output is correct |
6 |
Correct |
33 ms |
32212 KB |
Output is correct |
7 |
Correct |
27 ms |
32236 KB |
Output is correct |
8 |
Correct |
27 ms |
32252 KB |
Output is correct |
9 |
Correct |
32 ms |
32380 KB |
Output is correct |
10 |
Correct |
27 ms |
32380 KB |
Output is correct |
11 |
Correct |
25 ms |
32380 KB |
Output is correct |
12 |
Correct |
27 ms |
32380 KB |
Output is correct |
13 |
Correct |
30 ms |
32380 KB |
Output is correct |
14 |
Correct |
31 ms |
32380 KB |
Output is correct |
15 |
Correct |
26 ms |
32380 KB |
Output is correct |
16 |
Correct |
28 ms |
32380 KB |
Output is correct |
17 |
Correct |
26 ms |
32380 KB |
Output is correct |
18 |
Correct |
26 ms |
32380 KB |
Output is correct |
19 |
Correct |
33 ms |
32380 KB |
Output is correct |
20 |
Correct |
25 ms |
32380 KB |
Output is correct |
21 |
Correct |
38 ms |
32380 KB |
Output is correct |
22 |
Correct |
49 ms |
32380 KB |
Output is correct |
23 |
Correct |
41 ms |
32380 KB |
Output is correct |
24 |
Correct |
117 ms |
32508 KB |
Output is correct |
25 |
Correct |
109 ms |
32508 KB |
Output is correct |
26 |
Correct |
95 ms |
32508 KB |
Output is correct |
27 |
Correct |
123 ms |
32508 KB |
Output is correct |
28 |
Correct |
68 ms |
32508 KB |
Output is correct |