Description
对于所有长度为 \(n\) 的 \(2^n\) 个 01 串，对每个求出形如 000...111 的最长的子序列的长度，求出长度和。
Solution
记 \(a_i\) 表示前 \(i\) 个数中 \(0\) 的个数，\(b_i\)表 示 \(i\) 及其以后 \(1\) 的个数。那么对于一个 01 串，它的最长合法子序列长度就是
\[\max_{i=1}^{n+1}\{a_{i-1}+b_{i}\}
\]
对每个位置，我们都求出 \(a_{i-1}+b_{i}\) 的值，就得到一个新的数列。于是我们建立了一个 01 串到这个序列的双射。
容易发现这个序列的特点，首项就是 1 的个数，末项就是 0 的个数。所以总有 \(首项+末项=n\)。以及，相邻两项会且仅会相差 1（卡特兰既视感）。所以我们可以考虑枚举这个序列的最大值，以及首尾项，再通过组合计数解决。
假设峰值是 \(j(j\leq n)\)，首项是 \(i\)，那么问题就等价于从 \((0,i)\) 走到 \((n,n-i)\) 且最大不超过 \(j\)，最小不低于 \(0\) 的方案数。作 \((\frac{x-y}{2},\frac{x+y}{2})\) 的变换，再平移一下。问题就转化为从 \((0,0)\) 开始走，不接触 \(y=x+k_1\) 和 \(y=x+k_2\) 且最终到达 \((X,Y)\) 的方案数。转化为经典的双直线翻折法 [JLOI2015] 骗我呢。
#include<stdio.h>
#include<algorithm>
using namespace std;
#define ll long long
inline int read(){
int x=0,flag=1; char c=getchar();
while(c<'0'||c>'9'){if(c=='-')flag=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
return flag*x;
}
const int N=5e3+7;
int Mod;
ll fac[N<<2],ifac[N<<2],inv[N<<2],f[N][N];
inline ll C(int x,int y){return x<y? 0:fac[x]*ifac[y]%Mod*ifac[x-y]%Mod;}
inline void fold(int &x,int &y,bool typ,int op,ll &ans,int &j,int &k){
swap(x,y); int dt=typ? -k+1:-(j+1);
x+=dt,y-=dt; ans=(ans+Mod+op*(x>=0&&y>=0? C(x+y,x):0))%Mod;
}
inline ll calc(int X,int Y,int j,int k){
ll ans=C(X+Y,X);
int x=X,y=Y;
while(x>=0&&y>=0)
fold(x,y,0,-1,ans,j,k),fold(x,y,1,1,ans,j,k);
x=X,y=Y;
while(x>=0&&y>=0)
fold(x,y,1,-1,ans,j,k),fold(x,y,0,1,ans,j,k);
return ans;
}
ll F(int n,int i,int j,int k){
if(i>j) return 0;
if(~f[i][j]) return f[i][j];
return f[i][j]=calc((n-i)/2,(n+i)/2,j,k);
}
ll qpow(ll x,ll y){
ll ret=1;
while(y){
if(y&1) ret=ret*x%Mod;
y>>=1,x=x*x%Mod;
}
return ret;
}
int main(){
int T=read();
fac[0]=inv[1]=ifac[0]=1;
while(T--){
int n=read(); Mod=read();
for(int i=1;i<=2*n;i++) fac[i]=fac[i-1]*i%Mod;
for(int i=2;i<=2*n;i++) inv[i]=(Mod-Mod/i)*inv[Mod%i]%Mod;
for(int i=1;i<=2*n;i++) ifac[i]=ifac[i-1]*inv[i]%Mod;
ll ans=0;
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++) f[i][j]=-1;
for(int i=0;i<=n;i++){
int I=abs(i-(n-i)),rg=min(i,n-i);
for(int j=max(i,n-i);j<=n;j++)
ans=(ans+(F(n,I,j-rg,-rg)-F(n,I,j-rg-1,-rg)+Mod)%Mod*j%Mod)%Mod;
}
printf("%lld\n",ans);
printf("%lld\n",ans*qpow(qpow(2ll,Mod-2),n)%Mod);
}
}