CodeForces 785D Anton and School - 2

wander lv.2

发布时间：2023-10-21 21:16:56 328

相关标签：

题目链接：http://codeforces.com/contest/785/problem/D
题意：给你一个字符串只包含’(‘和’)’，让你重新组成一个字符串，这个字符串的左边必须全部为）右边必须全部为（，问你有多少种这样的字符串
解析：先前缀和的方式处理出到第i个字符位置他前面有多少个’(‘，他后面有多少个’)’，处理好以后，剩下的就是枚举位置i，然后组合数运算

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 2e5+100;
const int inf = 0x7fffffff;
const int mod = 1e9+7;
typedef long long ll;
char a[maxn];
int sum1[maxn],sum2[maxn];
ll jiec[maxn];
void init(int n)
{
    jiec[0] = 1;
    for(int i=1;i<=n;i++)
        jiec[i] = (jiec[i-1]*i)%mod;
    memset(sum1,0,sizeof(sum1));
    memset(sum2,0,sizeof(sum2));
}
ll qpow(ll x,ll n)
{
    int res = 1;
    while(n)
    {
        if(n&1)
            res = res*x%mod;
        x = x*x%mod;
        n>>=1;
    }
    return res;
}
ll inv(ll a)
{
    return qpow(a,mod-2);
}
ll slove(int a,int b)
{
    if(b>a)
        return 0;
    if(b==0)
        return 1;
    return (jiec[a]*inv((jiec[a-b]*jiec[b])%mod))%mod;
}
int main()
{
    scanf("%s",a+1);
    int len = strlen(a+1);
    init(len);
    for(int i=1;i<=len;i++)
    {
        if(a[i]=='(')
            sum1[i] = sum1[i-1]+1;
        else
            sum1[i] = sum1[i-1];
        if(a[len-i+1]==')')
            sum2[len-i+1] = sum2[len-i+2]+1;
        else
            sum2[len-i+1] = sum2[len-i+2];
    }
    ll ans = 0;
    for(int i=1;i<=len;i++)
    {
        if(a[i]=='(')
        {
            int t1 = sum1[i];
            int t2 = sum2[i];
            ans = (ans+slove(t1+t2-1,t2-1))%mod;
        }
    }
    printf("%I64d\n",ans);
    return 0;
}

文章来源： https://blog.51cto.com/u_11435021/5879903

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。