Codeforces 785D - Anton and School - 2 - [范德蒙德恒等式][快速幂+逆元]

题目链接：https://codeforces.com/problemset/problem/785/D

题解：

首先很好想的，如果我们预处理出每个 "(" 的左边还有 $x$ 个 "("，以及右边有 $y$ 个 ")"，那么就有式子如下：

　　① 若 $x+1 \le y$：$C_{x}^{0} C_{y}^{1} + C_{x}^{1} C_{y}^{2} + \cdots + C_{x}^{x} C_{y}^{x+1} = \sum_{i=0}^{x} C_{x}^{i} C_{y}^{i+1}$

　　② 若 $x+1 > y$：$C_{x}^{0} C_{y}^{1} + C_{x}^{1} C_{y}^{2} + \cdots + C_{x}^{y-1} C_{y}^{y} = \sum_{i=0}^{y-1} C_{x}^{i} C_{y}^{i+1}$

然后算一下，哦哟 $O(n^2)$ 的优秀算法，GG，想了半天也不知道咋优化，看了题解才知道是“范德蒙德恒等式”：

$\sum_{i=0}^{r} C_{m}^{i} C_{n}^{r-i} = C_{m+n}^{r}$

以及它的一个推导等式：

$\sum_{i=0}^{m} C_{m}^{i} C_{n}^{r+i} = C_{m+n}^{m+r}$

① 直接用推导等式可以得到：

$\sum_{i=0}^{x} C_{x}^{i} C_{y}^{i+1} = C_{x+y}^{x+1}$

而 ② 则用范德蒙德恒等式得到：

$\sum_{i=0}^{y-1} C_{x}^{i} C_{y}^{i+1} = \sum_{i=0}^{y-1} C_{x}^{i} C_{y}^{y-1-i} = C_{x+y}^{y-1}$

综上，就变成了：对于每个 "("，假设其左边还有 $x$ 个 "("，右边有 $y$ 个 ")"，那么对于答案的贡献：

　　① 若 $x+1 \le y$，则为 $C_{x+y}^{x+1}$

　　② 若 $x+1 > y$，则为 $C_{x+y}^{y-1}$

只要预处理出阶乘和阶乘的逆元，那么每次算 $C_{n}^{r}$ 就是 $O(1)$ 的。

AC代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod=1e9+;

const int maxn=2e5+;

char s[maxn];

int n,x[maxn],y[maxn];

ll fpow(ll a,ll n)

{

    ll res=, base=a%mod;

    while(n)

    {

        if(n&) res*=base, res%=mod;

        base*=base, base%=mod;

        n>>=;

    }

    return res%mod;

}

ll inv(ll a){return fpow(a,mod-);}

ll fac[maxn],fac_inv[maxn];

ll C(ll n,ll r)

{

    ll res=fac[n];

    res*=fac_inv[r], res%=mod;

    res*=fac_inv[n-r], res%=mod;

    return res;

}

int main()

{

    fac[]=, fac_inv[]=inv(fac[]);

    for(int i=;i<maxn;i++) fac[i]=fac[i-]*i%mod, fac_inv[i]=inv(fac[i]);

    scanf("%s",s+), n=strlen(s+);

    x[]=;

    for(int i=;i<=n;i++) x[i]=x[i-]+(s[i-]=='(');

    y[n]=;

    for(int i=n-;i>;i--) y[i]=y[i+]+(s[i+]==')');

    //for(int i=1;i<=n;i++) printf("%d %d\n",x[i],y[i]);

    ll ans=;

    for(int i=;i<=n;i++)

    {

        if(s[i]!='(') continue;

        if(y[i]<=) continue;

        if(x[i]+<=y[i])

            ans+=C(x[i]+y[i],x[i]+), ans%=mod;

        else

            ans+=C(x[i]+y[i],y[i]-), ans%=mod;

    }

    cout<<ans<<endl;

}

巴特西

Codeforces 785D - Anton and School - 2 - [范德蒙德恒等式][快速幂+逆元]

最新文章

热门文章