#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int mod = 1E9 + 7;
const int _N = 2500;
i64 dp[_N][_N];
/*
dp[i][j] = 已经排了i个数,连通块=j
放入某个块: dp[i][j]=dp[i-1][j]*j
新加一个块: dp[i][j]=dp[i-1][j-1]*j
合并两个块: dp[i][j]=dp[i-1][j+1]*j
若i==A || i==B, 我们不可以用来合并而且也不能随便加入块:
dp[i][j] = dp[i-1][j]
dp[i][j] = dp[i-1][j-1]
*/
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int N, A, B; cin >> N >> A >> B;
dp[1][1] = 1;
for (int i = 2; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (i == A || i == B) {
dp[i][j] += dp[i - 1][j];
dp[i][j] += dp[i - 1][j - 1];
dp[i][j] %= mod;
continue;
}
int cnt = 2;
dp[i][j] += dp[i - 1][j - 1] * (j - cnt);//不能放头,不能放尾
dp[i][j] %= mod;
dp[i][j] += dp[i - 1][j + 1] * j;
dp[i][j] %= mod;
}
}
cout << dp[N][1] << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |