CodeForces 785 D Anton and School - 2 范德蒙恒等式

清疚 2021-12-16 01:27 202阅读 0赞

[Anton and School - 2][]

题解：

枚举每个左括号作为必选的。

那么方案数就应该是下面的 1 ， 然后不断化简， 通过范德蒙恒等式 ， 可以将其化为一个组合数。

![1327999-20190512191252742-1465964438.jpg][]

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
    #define LL long long
    #define ULL unsigned LL
    #define fi first
    #define se second
    #define pb push_back
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define lch(x) tr[x].son[0]
    #define rch(x) tr[x].son[1]
    #define max3(a,b,c) max(a,max(b,c))
    #define min3(a,b,c) min(a,min(b,c))
    typedef pair<int,int> pll;
    const int inf = 0x3f3f3f3f;
    const int _inf = 0xc0c0c0c0;
    const LL INF = 0x3f3f3f3f3f3f3f3f;
    const LL _INF = 0xc0c0c0c0c0c0c0c0;
    const LL mod =  (int)1e9+7;
    const int N = 2e5 + 100;
    int F[N], Finv[N], inv[N];/// F是阶层 Finv是逆元的阶层
    void init(){
        inv[1] = 1;
        for(int i = 2; i < N; i++)
            inv[i] = (mod - mod/i) * 1ll * inv[mod % i] % mod;
        F[0] = Finv[0] = 1;
        for(int i = 1; i < N; i++){
            F[i] = F[i-1] * 1ll * i % mod;
            Finv[i] = Finv[i-1] * 1ll * inv[i] % mod;
        }
    }
    int comb(int n, int m){ /// C(n,m)
        if(m < 0 || m > n) return 0;
        return F[n] * 1ll * Finv[n-m] % mod * Finv[m] % mod;
    }
    char s[N];
    int l[N], r[N];
    int main(){
        scanf("%s", s+1);
        int n = strlen(s+1);
        for(int i = 1; i <= n; ++i){
            if(s[i] == '(') l[i]++;
            l[i] += l[i-1];
        }
        for(int i = n; i >= 1; --i){
            if(s[i] == ')') r[i]++;
            r[i] += r[i+1];
        }
        LL ans = 0;
        init();
        for(int i = 1; i <= n; ++i){
            if(s[i] == '('){
                ans = (ans + comb(l[i]-1+r[i], l[i]))%mod;
            }
        }
        cout << ans << endl;
        return 0;
    }

转载于:https://www.cnblogs.com/MingSD/p/10853280.html

[Anton and School - 2]: http://codeforces.com/contest/785/problem/D
[1327999-20190512191252742-1465964438.jpg]: /images/20211214/1c1dd60e12044881aaa70f8a76355570.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211214/625b5342ead74a13ab3f818fe7ab8c44.png