CF1750F Majority

题目描述

每个人都在愉快地编程，直到突然发生了电力短缺，最好的竞赛编程网站宕机了。幸运的是，系统管理员最近购买了一些新设备，包括一些 UPS。因此，仍有一些服务器在线，但我们需要所有服务器都正常工作，才能让本轮比赛计分。

可以将服务器看作一个长度为 $n$ 的二进制字符串 $s$。如果第 $i$ 台服务器在线，则 $s_i=1$，否则 $s_i=0$。

系统管理员可以进行如下称为“电力传播”的操作，操作包括以下几个阶段：

• 选择两个位置为 $1\le i<j\le n$ 的服务器，且这两台服务器都在线（即 $s_i=s_j=1$）。传播只能从在线服务器开始。
• 检查是否有足够的电力进行传播。我们认为在区间 $[i,j]$ 内，若开启的服务器数量不少于关闭的服务器数量，则有足够的电力。更形式化地说，检查是否满足 $2\cdot (s_i+s_{i+1}+\dots +s_j)\ge j-i+1$。
• 如果检查通过，则将区间 $[i,j]$ 内所有离线服务器全部开启。更形式化地说，对所有 $k$ 从 $i$ 到 $j$，令 $s_k:=1$。

我们称长度为 $n$ 的二进制字符串 $s$ 是“计分的”，如果可以通过若干次（可能为 $0$ 次）电力传播操作，将所有服务器都开启（即对所有 $1\le i\le n$，有 $s_i=1$）。你的任务是计算长度为 $n$ 的计分二进制字符串的数量，结果对 $m$ 取模。

输入格式

第一行包含两个整数 $n$ 和 $m$（$1\le n\le 5000$，$10\le m\le 10^9$），分别表示字符串的长度和取模的数。

输出格式

输出一个整数，表示长度为 $n$ 的计分二进制字符串的数量。由于答案可能很大，请输出对 $m$ 取模后的结果。

输入输出样例 #1

输入 #1

2 100

输出 #1

1

输入输出样例 #2

输入 #2

3 10

输出 #2

2

输入输出样例 #3

输入 #3

4 3271890

输出 #3

4

输入输出样例 #4

输入 #4

17 123456

输出 #4

32347

说明/提示

在第一个样例中，唯一的计分字符串是 11。所以答案是 $1$。

在第二个样例中，计分字符串有：

• 111；
• 101，因为可以对 $i=1$，$j=3$ 进行一次操作。

所以答案是 $2$。

在第三个样例中，计分字符串有：

• 1001；
• 1111；
• 1011；
• 1101。

所以答案是 $4$。

由 ChatGPT 4.1 翻译

思路

提示：

1. 考虑容斥原理
2. 设f[i][j]表示总共i个服务器，操作所有可操作后最后的全1序列长度为j
3. 思考如何转移，容斥f[i][i]=

考虑到f[i][j]是可以在f[j][j]基础上增加一个0序列在前和一个包含1的序列
设0序列长o，1序列长p，则j+p<o，j+o<i，f[i][j]+=f[j][j]f[i-j-o][p]
直接推出(i-j-o)+p<i-2j，于是前缀和即可。

代码

#include<bits/stdc++.h> 
using namespace std;
long long n,m,p2[500005],f[5005][5005],ok[200005],oc[200005],mod;
int main(){
    cin>>n>>m;
    mod=m;
    p2[0]=1;
    for(int i=1;i<=n;i++){
        p2[i]=p2[i-1]*2ll%mod;
    }
    f[1][1]=1;
    ok[2]=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=2*n;j++){
            oc[j]=(oc[j-1]+ok[j])%mod;
        }
        f[i][i]=p2[i-2];
        for(int j=1;j+j<=(i-1);j++){
            f[i][j]=(f[j][j]*oc[i-j*2-1])%mod;
            f[i][i]=((f[i][i]-f[i][j])%mod+mod)%mod;
        }
        for(int j=1;j<=i;j++){
            ok[i+j]=(ok[i+j]+f[i][j])%mod;
        }
    }
    cout<<f[n][n]<<endl;
	return 0; 	
}//>>AKIOI<<//