传送门：https://codeforces.com/contest/1515/problem/E 赛中想了一个多小时，还是处理不了一些细节。
题意
有n个电脑排在一排，你可以手动打开任意电脑，但是有个特点， 对于一个电脑，如果它左右都被打开了，那么它会自动打开。
最后问，有多少种全部开机方案？
思路
我们考虑两种方式，第一种全部都是手动打开，第二种带有自动打开。
对于电脑1，如果要全部手动开启，则需要按照1，2…n的顺序打开，$C_{n-1}^0$ 对于电脑2，如果要全部手动开启，则后面必须按照3,4..n的顺序，前面必须1，$C_{n-1}^1$ 对于电脑k，如果要全部手动开启，则后面必须要按照k+1,k+2…n的顺序，前面必须是k-1,…1的顺序，所有要在n-1中选k-1个开前面，$C_{n-1}^{k-1}$
则总方案数为$C_{n-1}^0+C_{n-1}^1+…+C_{n-1}^{n-1}=2^{n-1}$
也就是说，对于x台电脑，如果全部手动开启的话，有$2^{x-1}$种方案数，下面会用到。
自动打开只会出现现在左右都打开后才会自动打开，所以假设这么一种开机方式： 设有$x_k$台电脑自动开启。 1到$x_1-1$手动打开，$x_1+1$到$x_2-1$手动打开，…$x_k+1$到n手动打开。$(x_k+1\leq N)$ 这样，$x_k$台都满足自动打开的要求。
然后就是要怎么进行这个过程。
设f[i][j]为前i台电脑中，有j台是手动打开，第i台也是手动打开，并且第i+1台自动开启的方案数。
则我们想让第i+1台成为自动打开的电脑，则i+1后面几台电脑手动打开，设为k台。
则就是f[i][j]向f[i+1+k][j+k]的转移，怎么转移呢？
f[i+1+k][j+k]比f[i][j]多了k台手动开启。 这k台我们称为“新”打开的电脑，j台我们称为“旧”打开的电脑。 第i+1是自动打开的。 之前我们处理过，k台手动开启的方案数为$2^{k-1}$，然后我们要将k台和j台一起合并。 那么就是有j+k台中，有k台是“新”电脑，方案数为$C_{k+j}^k$。
则转移方程为$f[i+1+k][j+k]=f[i][j]*2^{k-1}*C_{j+k}^k。$
i、j、k三层循环进行转移，$O(n^3)$是可以的。
最后预处理组合数进行转移即可。
Code(436MS)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| ##include "bits/stdc++.h"
using namespace std;
typedef long long ll;
ll n, mod;
const int N = 410;
ll F[N], invn[N], invF[N], bit[N];
void init() {
bit[1] = F[0] = F[1] = invn[0] = invn[1] = invF[0] = invF[1] = 1;
for(int i = 2;i < N; i++){
F[i] = F[i - 1] * i % mod;
invn[i] = (mod - mod / i) * invn[mod % i] % mod;
invF[i] = invF[i - 1] * invn[i] % mod;
bit[i] = bit[i - 1] * 2 % mod;
}
}
ll C(ll m, ll n) {
if(m < 0 n < 0 n > m)
return 0;
ll ans = F[m];
ans = ans * invF[n] % mod;
ans = ans * invF[m - n] % mod;
return ans;
}
void solve() {
cin >> n >> mod;
init();
vector<vector<ll>> dp(n + 1, vector<ll>(n + 1, 0));
for(int i = 1;i <= n; i++) {
dp[i][i] = bit[i];
for(int j = 0;j <= i; j++) {
for(int k = 1;k + i + 1 <= n; k++) {
dp[i + 1 + k][j + k] = (dp[i + 1 + k][j + k] + dp[i][j] * bit[k] % mod * C(j + k, k) % mod) % mod;
}
}
}
ll ans = 0;
for(int i = 0;i <= n; i++) {
ans = (ans + dp[n][i]) % mod;
}
cout << ans << endl;
}
signed main() {
solve();
}
|