#include<bits/stdc++.h>
using namespace std;
#define int long long
int mod = 1e9+7;
int32_t main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
int n, a, b;
cin >> n >> a >> b;
vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
dp[1][1] = 1;
int bb = 0;
if (a==1) bb++;
if (b==1) bb++;
for (int i = 2; i <= n; i++)
{
if (i==a)
{
dp[i] = vector<int>(dp[i-1]);
i++;
bb++;
}
if (i==b)
{
if (n%2==0)
{
for (int j = 2; j <= n; j++)
{
dp[i][j] += dp[i-1][j-1];
}
}
else
{
dp[i] = vector<int>(dp[i-1]);
}
i++;
bb++;
}
if (i==a)
{
dp[i] = vector<int>(dp[i-1]);
i++;
bb++;
}
if (i>n) break;
for (int j = 2; j <=n; j++)
{
dp[i][j] += dp[i-1][j-1]*(j);
dp[i][j] -= dp[i-1][j-1]*bb;
dp[i][j-1] += dp[i-1][j]*(j-1);
}
for (int j = 1; j <= n; j++) dp[i][j]%=mod;
}
int sol = dp[n][1];
dp.assign(n+1, vector<int>(n+1, 0));
dp[1][1] =1;
bb=0;
if (a==1) bb++;
if (b==1) bb++;
for (int i = 2; i <= n; i++)
{
if (i==a)
{
for (int j = 2; j <= n; j++)
{
dp[i][j] += dp[i-1][j-1];
}
i++;
bb++;
}
if (i==b)
{
if (n%2)
{
for (int j = 2; j <= n; j++)
{
dp[i][j] += dp[i-1][j-1];
}
}
else
{
dp[i] = vector<int>(dp[i-1]);
}
i++;
bb++;
}
if (i==a)
{
for (int j = 2; j <= n; j++)
{
dp[i][j] += dp[i-1][j-1];
}
i++;
bb++;
}
if (i>n) break;
for (int j = 2; j <=n; j++)
{
dp[i][j] += dp[i-1][j-1]*(j);
dp[i][j] -= dp[i-1][j-1]*bb;
dp[i][j-1] += dp[i-1][j]*(j-1);
}
for (int j = 1; j <= n; j++) dp[i][j]%=mod;
}
cout << (sol + dp[n][1])%mod;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
600 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
1 ms |
604 KB |
Output is correct |
17 |
Correct |
1 ms |
604 KB |
Output is correct |
18 |
Correct |
1 ms |
604 KB |
Output is correct |
19 |
Correct |
1 ms |
604 KB |
Output is correct |
20 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
604 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
600 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
1 ms |
604 KB |
Output is correct |
17 |
Correct |
1 ms |
604 KB |
Output is correct |
18 |
Correct |
1 ms |
604 KB |
Output is correct |
19 |
Correct |
1 ms |
604 KB |
Output is correct |
20 |
Correct |
1 ms |
604 KB |
Output is correct |
21 |
Correct |
5 ms |
3676 KB |
Output is correct |
22 |
Correct |
6 ms |
4272 KB |
Output is correct |
23 |
Correct |
6 ms |
4784 KB |
Output is correct |
24 |
Correct |
44 ms |
31836 KB |
Output is correct |
25 |
Correct |
49 ms |
31832 KB |
Output is correct |
26 |
Correct |
47 ms |
31836 KB |
Output is correct |
27 |
Correct |
45 ms |
31580 KB |
Output is correct |
28 |
Correct |
26 ms |
18064 KB |
Output is correct |