Codeforces Global Round 14 E. Phoenix and Computers dp+排列组合

传送门：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++) { // 前i台电脑
        dp[i][i] = bit[i];
        for(int j = 0;j <= i; j++) { // i台中有j台是手动打开的
            for(int k = 1;k + i + 1 <= n; k++) { // i + 1是自动打开的，然后后面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();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/05/03/codeforces-global-round-14-e-phoenix-and-computers/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！