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

· · 题解

前言

被这个题成功卡爆了一晚上，水平有待提升。

Solution

考虑一个合法的整数序列 a 满足以下条件：a_1=0 且 \forall 2\le i \le n,1\le a_i \le a_{i-1}+1。

于是我们只需要计算每一段 -1 的贡献然后乘一起即可。

设 a_l=x,a_r=y，中间一段都是 -1，我们可以先设置段内的 a_i=x+i-l，然后从左到右考虑在满足条件的前提下对段内的一段后缀减去某个非负整数。

考虑上述与一个经典二维格点路径计数问题等价：给定起点 S(0,-a_l) 和终点 T(r-l-1,r-l-a_r)，要求只能走到 (x,y+1) 或 (x+1,y)，且不能经过满足 x<y 的点，求合法路径的方案数。

我们可以将直线 y=x+1 作为分界线，作出点 S 的对称点，也就是 S'(-1-a_l,1)。

设 f(A,B) 表示无 x<y 约束下从 A 点走到 B 点的方案数，那么有 x<y 约束下从 S 点走到 T 点的方案数为 f(S,T)-f(S',T)。

如果 a_n=-1，枚举 a_n 的合法值计数即可，于是这题就做完了。

const ll mod=1e9+7;
ll fac[N],inv[N];
ll a[N],n;

ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll ksm(ll x,ll y){
    ll p=1;
    while(y){
        if(y&1) p=p*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return p;
}
ll C(int u,int v){
    if(u<v || u<0 || v<0) return 0;
    return fac[u]*inv[v]%mod*inv[u-v]%mod;
}
ll sol(int l,int r){
    int x1=0,y1=-a[l],x2=r-l-1,y2=x2-a[r]+1;
    ll now=0;
    now=(now+C(x2-x1+y2-y1,x2-x1))%mod;
    x1=-(1-y1),y1=1;
    now=(now-C(x2-x1+y2-y1,x2-x1)+mod)%mod;
    return now;
}

int main()
{
    //freopen("gcx.in","r",stdin);
    //freopen("gcx.out","w",stdout);
    fac[0]=1;
    For(i,1,N-1) fac[i]=fac[i-1]*i%mod;
    inv[N-1]=ksm(fac[N-1],mod-2);
    Rof(i,N-2,0) inv[i]=inv[i+1]*(i+1)%mod;
    n=read();
    For(i,1,n) a[i]=read();
    if(a[1]>0){
        cout<<0;
        return 0;
    }
    a[1]=0;
    ll ans=1;
    int lst=1;
    For(i,2,n){
        if(a[i]!=-1){
            ans=ans*sol(lst,i)%mod;
            lst=i;
        }
    }
    if(a[n]==-1){
        ll sum=0;
        For(i,1,n){
            a[n]=i;
            sum=(sum+sol(lst,n))%mod;
        }
        ans=ans*sum%mod;
    }
    cout<<ans;
    return 0;
}