CF1515E 题解

· · 题解

一个 O(n^2) 甚至可能 O(n \log n)（？）的，不需要用到生成函数知识的组合数学简短新解法。

结论先行：

\text{Ans}=\sum_{k=1}^{\lfloor \frac{(n+1)}{2} \rfloor} k! \cdot S(n-k+1,k) \cdot2^{n-2k+1}

观察最终情况。可以发现其由若干个由手动开启的电脑的连续的块组成。而且这些块之间必须由恰好一台自动开启的电脑隔开。

也就是：

一段手动开启 + 一个自动开启 + 一段手动开启 + ⋯ + 一个自动开启 + 一段手动开启

假设有 k 个手动开启的块。尝试固定 k 进行计数。

则自动开启的电脑数量为 k-1，手动开启的电脑总数为 A=n-k+1。

我们现在有 k 个手动开启的块，共需要手动开启 A 次。既然不同块之间的开启操作是可以互相穿插的，我们可以把问题转化为：将 A 个不同的时间戳（即第 1 次操作，第 2 次操作…第 A 次操作），分配给 k 个有序且非空的块。

引入经典结论：

将 A 个不同的元素放入 k 个有序且非空的集合中，方案数等于 k! \cdot S(A,k)，其中 S(n,m) 是第二类斯特林数。

这便解决完了不同块之间操作顺序的分配的方案数。

我们来看块内的。

对于一个长度为 c 的手动开启的块，将其合法开启的顺序有 2^{c-1} 种。

注意这里不是 c!，因为你需要防止这个需要全部被手动开启的块内出现自动开启的电脑。也就是说，在这一个块内，\{1,3\} 这个开启顺序是不合法的，因为这样会让电脑 2 自动开启。

那我们倒着想。这个块内最后被开启的电脑一定位于这个块的两端（一共两种可能）。将其剥离之后，剩下的 c-1 台电脑依然需要满足相同的条件。递归下去，直到剩下最后 1 台电脑，此时最左边和最右是同一台电脑（一共一种可能）。

则合法开启一个块的顺序有

2 \times 2 \times \cdots \times 1=2^{c-1}

根据乘法原理，这 k 个块内部合法顺序数可以直接相乘。假设在某种时间戳分配方案下，第 i 个块分到了 c_i 个时间戳（即该块的长度为 c_i），对于固定的 k 和 A，无论这 A 次操作被划分成怎样的 k 个块（即无论 c_1, c_2, \dots, c_k 分别是多少），这个乘积始终为

2^{c_1-1} \times 2^{c_2-1} \times \cdots \times 2^{c_k-1} = 2^{\sum c_i-k} = 2^{A-k}

我们可以将其与前面的操作分配方案数直接相乘，得到对于固定 k 的总方案数为：

k! \cdot S(A,k) \cdot2^{A-k}

分析 k 的枚举界限。显然 k \ge 1。每个块内至少要有一台电脑，所以最后固定的 k 至少需要开启 k+(k-1)=2k-1 台电脑，它要 \le n，解之得 k \le \frac{(n+1)}{2}。

代入 A=n-k+1，则最终答案为

\text{Ans}=\sum_{k=1}^{\lfloor \frac{(n+1)}{2} \rfloor} k! \cdot S(n-k+1,k) \cdot2^{n-2k+1}

预处理第二类斯特林数即可 O(n^2) 计算。

#include <iostream>
using namespace std;

const int N = 405;
int n, M, ans;
int S[N][N], fac[N], p2[N]; 

int main() {
    cin >> n >> M;
    S[0][0] = fac[0] = p2[0] = 1;

    for (int i = 1; i <= n; i++) {
        fac[i] = 1ll * fac[i - 1] * i % M;
        p2[i] = 2ll * p2[i - 1] % M;
        for (int j = 1; j <= i; j++)
            S[i][j] = (S[i - 1][j - 1] + 1ll * j * S[i - 1][j]) % M;
    }

    for (int k = 1; k <= (n + 1) / 2; k++) {
        int A = n - k + 1;
        ans = (ans + 1ll * fac[k] * S[A][k] % M * p2[A - k]) % M;
    }

    cout << ans;
    return 0;
}

鉴于最终的答案式子非常的优美简洁，我猜测它可以在 O(n \log n) 的时间内通过多项式等技巧进行计算。不过那我就不会了……欢迎各位大神前来鞭挞。