自动搬运

查看原文

来自洛谷，原作者为

	gcx12012 每一个不曾起舞的日子，都是对生命的辜负。

搬运于2025-08-24 23:14:35，当前版本为作者最后更新于2025-04-25 09:44:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

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

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;
}