深度优先搜索 蓝桥杯 2024 国研究生组

[蓝桥杯 2024 国研究生组] 深度优先搜索

我不会卡特兰数。

给定长度 $n$ 的序列 $a$ 满足 $a_i\in[-1,n]$，求有多少种将 $-1$ 替换为 $[0,n]$ 任意数的方案使得：

• 有且仅有 $a_1=0$；
• 对于任意一个 $2\le i\le n$，有 $a_{i-1}+1\ge a_i$。

对 $10^9+7$ 取模。

套路的差分，令 $b_i=a_i-a_{i-1}$，则 $b_i\le 1$。

不妨分段考虑，即，考虑 $a_0,a_n\ne -1$，$a_i=-1$的弱化版。

那么首先我们有限制：

$$a_0+\sum b_i=a_n$$

由于 $b_i\le 1$ 不太好处理，我们不妨令 $c_i=1-b_i$，这样限制变为 $c_i\ge 0$，然后：

$$a_0=\sum 1-c_i=a_n$$

接着 $s_i$ 为 $c_i$ 的前缀和，那么上面的约束变为 $s_n=a_0-a_n+n$。

然而这还不够，我们还有这个限制：

$$a_0+\sum_{j\le i}b_i\ge 1$$

于是，将 $s_i$ 代换 $b_i$ 后得到 $s_i\le i+a_0-1$。

接下来最精彩的一步！将上述限制转化为如下场景：

初始在 $(0,0)$，每次向右边走一步，然后向上走 $c_i$ 步，不能碰到直线 $y=x+a_0$，终点 $(n,s_n)$，求方案数。

这是一个经典的反射容斥问题，使用你精湛的反射容斥技巧就能解决。

上述简化版解决后，剩下的就是分段转移了，十分简单。

#include <bits/stdc++.h>
using namespace std;
const int N=3001000,P=1000000007;
int n,a[N],fac[N],inv[N],am[N],ss;
int kpow(int a,int b){
    int t=1;
    while(b){
        if(b&1)t=1ll*t*a%P;
        a=1ll*a*a%P;
        b>>=1;
    }
    return t;
}
void init(int n){
    fac[0]=1;
    for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%P;
    inv[n]=kpow(fac[n],P-2);
    for(int i=n-1;~i;i--)inv[i]=1ll*inv[i+1]*(i+1)%P;
}
int C(int n,int m){return n<m?0:1ll*fac[n]*inv[m]%P*inv[n-m]%P;}
int calc(int l,int r){
    if(l+1==r)return a[l]+1>=a[r]?1:0;
    return (C(a[l]-a[r]+2*(r-l)-1,r-l-1)-C(a[l]-a[r]+2*(r-l)-1,r-l-1-a[r])+P)%P;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    init(n*3);
    if(a[1]!=0&&a[1]!=-1)return puts("0"),0;
    a[1]=0;
    for(int i=1;i<=n;i++)if(a[i]>=0)am[++ss]=i;
    int ans=1;
    for(int i=2;i<=ss;i++)ans=1ll*ans*calc(am[i-1],am[i])%P;
    if(a[n]==-1){
        int res=0;
        for(int i=1;i<=n;i++)
            a[n]=i,(res+=calc(am[ss],n))%=P;
        ans=1ll*ans*res%P;
    }
    printf("%d",ans);
    return 0;
}