CF1696E Placing Jinas 题解

· · 题解

可能更好的阅读体验

题目传送门

upd on 2022.9.13：好像有点小问题在评论里面被指出，已经修改。

题目大意

给定一个 单调不增 的序列 a，第 0 到 n 项为 a_1,a_2,\dots,a_n，之后的为全 0。
对平面直角坐标系上的每个整点进行染色，对于一个点 (x,y) 如果 y<a_x 那么这个点位白色，否则为黑色。
每次操作你可以使点 (x,y) 上的娃娃数量减一，同时 (x,y+1) 和 (x+1,y) 上的娃娃数量都会加一。
现在在 (0,0) 上有一个娃娃，求让所有的白色点上都没有娃娃的操作数量，对 10^9+7 取模。

n\le 2\times10^5,0\le a_i\le 2\times10^5

题目解析

设 f(x,y) 为对点 (x,y) 实行的操作次数。
我们发现，当 x=0 或者是 y=0 的时候，f(x,y)=1，否则 f(x,y)=f(x-1,y)+f(x,y-1)。
我们发现这个递推式像杨辉三角的递推式，不难得到 f(x,y)=C_{x+y}^{x}。

那么答案就是

\sum_{i=0}^{n}\sum_{j=0}^{a_i-1}f(i,j)

但是这样求是 O(n^2) 的，所以需要考虑化简这个式子。
注意到

\begin{aligned} & \sum_{i=0}^{n}f(x,i)\\ = & f(x,0)+f(x,1)+f(x,2)+ f(x,3)+\cdots+f(x,n)\\ = & f(x+1,0)+f(x,1)+f(x,2)+ f(x,3)+\cdots +f(x,n)\\ = & f(x+1,1)+f(x,2)+ f(x,3) + \cdots f(x,n) \\ \vdots &\\ = & f(x+1,n) \end{aligned}

所以答案就是

\begin{aligned} & \sum_{i=0}^{n}\sum_{j=0}^{a_i-1}f(i,j)\\ = & \sum_{i=0}^{n}f(i+1,a_i-1)\\ = & \sum_{i=0}^{n}C_{a_i+i}^{i+1} \end{aligned}

代码：

int n,a[maxn]; ll fact[maxn],inv[maxn],ans;
ll mpow(ll x,ll y){
    ll res=1,tmp=x%MOD;
    while(y){
        if(y&1) res=res*tmp%MOD;
        y>>=1; tmp=tmp*tmp%MOD;
    } return res;
}
void init(){
    int i; inv[0]=fact[0]=1; for(i=1;i<=N;i++) fact[i]=fact[i-1]*i%MOD;
    inv[N]=mpow(fact[N],MOD-2); for(i=N-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%MOD; return;
}
ll C(int x,int y){ return fact[x]*inv[y]%MOD*inv[x-y]%MOD; }
int main(){
    n=read(); int i; for(i=0;i<=n;i++) a[i]=read(); init();
    for(i=0;i<=n;i++) if(a[i]>=1) ans+=C(a[i]+i,i+1),ans%=MOD;
    print(ans%MOD); return 0;
}