题解 CF1750F 【Majority】

· · 题解

直接考虑合法条件似乎不太方便，考虑来观察一下一个长为 n 的 01 串不合法的条件。

考虑 dp，设 dp_{i, j} 表示长为 i，钦定两端为 1，一直操作直到不能再操作时最后一个 1 连续段长度为 j 的方案数。

初值：dp_{1, 1} = 1。

转移：对于 dp_{i, i}，考虑容斥，则有：dp_{i, i} = 2^{i - 2} - \displaystyle\sum_{j = 1}^{\lfloor \frac{i - 1}{2} \rfloor} dp_{i, j}。

对于其他 dp_{i, j}，考虑在 dp_{j, j} 的基础上在前面依次添加一个 0 连续段和一个 1 连续段，则：dp_{i, j} = dp_{j, j} \displaystyle\sum_{k = j + 2}^{i - j - 1} \sum_{l = 1}^{k - j - 1} dp_{i - j - k, l}（后面这两坨本来是 j + k < i, j + l < k，这个限制可以被改写为 (i - j - k) + l < i - 2j）。

答案：dp_{n, n}。

前缀和优化 dp 即可。具体地，维护一个 sum_i 表示所有满足 j + k \leq i 的 dp_{i, j} 之和。

时间复杂度为 O(n^2)。

代码：

#include <stdio.h>

typedef long long ll;

int power[5007];
ll dp[5007][5007], sum1[10007], sum2[10007];

inline void init(int n, int m){
    power[0] = 1;
    for (int i = 1; i <= n; i++){
        power[i] = power[i - 1] * 2 % m;
    }
}

int main(){
    int n, m, k;
    scanf("%d %d", &n, &m);
    init(n, m);
    k = n * 2;
    dp[1][1] = sum1[2] = 1;
    for (int i = 2; i <= n; i++){
        for (int j = 1; j <= k; j++){
            sum2[j] = (sum2[j - 1] + sum1[j]) % m;
        }
        dp[i][i] = power[i - 2];
        for (int j = 1; j * 2 < i; j++){
            dp[i][j] = dp[j][j] * sum2[i - j * 2 - 1] % m;
            dp[i][i] = ((dp[i][i] - dp[i][j]) % m + m) % m;
        }
        for (int j = 1; j <= i; j++){
            int t = i + j;
            sum1[t] = (sum1[t] + dp[i][j]) % m;
        }
    }
    printf("%lld", dp[n][n]);
    return 0;
}