题解【[JDWOI-2] 括号串】

kouylan · 2021-07-06 00:05:19 · 个人记录

首先很明显的，最多匹配的括号对数就是 \lfloor\frac{n}{2}\rfloor，记为 m。

如果 n 是偶数，问题就转化成了有 m 对括号，要组成合法括号串的方案数，用卡特兰数即可。

如果 n 是奇数，我们还是可以先求出 m 组括号的合法括号串的个数，然后把问题转化成往合法括号串中插入一个 '(' 或者 ')' 的方案数。因为此处左右括号对称，所以插入左、右括号的方案数相等。此处我们仅以插入右括号为例。

先抛结论：

记 '(' 为 +1，')' 为 -1，对于每一个括号串可以得到一个前缀和数组 a，只有当 a_i=0 时，这个位置才能插入右括号保证不重复也不遗漏。

大概证明：

如果在 a_i\neq 0 的位置插入右括号，那前 i 位依然合法，加上右括号后必定可以在其他串中找到与之相同的前缀，这样就重复了。

所以说，我们现在要求出对于 m 对括号的所有括号串，一共有多少个位置满足 a_i=0。

我们考虑对于每一个 i，有多少括号串存在 a_i=0。如果在第 i=2k 位 a_i=0，那么可以从这一位拆开，使得前后变成两个独立的合法括号串，前者有 k 对括号，后者有 (m-k) 个括号，所以 a_i=0 的括号串有 catalan(k)\times catalan(m-k) 个。

把这些位全都加起来，这样的位置总个数是

这样所有值都能 O(n) 预处理出来，查询就做到了 O(1) 计算。

下面是 std (by kouylan)

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 4e6;

int Q,M,n,ans,fac[4000005],inv[4000005],cat[4000005],inv1[4000005];

int ksm(int x,int w)
{
    int s=1;
    while(w)
    {
        if(w&1)
            s = s*x%M;
        x = x*x%M;
        w >>= 1; 
    }
    return s;
}

signed main()
{
    cin>>Q>>M;
    fac[0] = 1;
    for(int i=1;i<=N+2;fac[i]=fac[i-1]*i%M,i++);
    inv[N+2] = ksm(fac[N+2],M-2);
    for(int i=N+1;i>=1;i--)
        inv[i] = inv[i+1]*(i+1)%M;
    inv[0] = 1;
    inv1[1] = 1;
    for(int i=2;i<=N+2;i++)
        inv1[i] = M-M/i*inv1[M%i]%M;
    cat[1] = 1;
    for(int i=2;i<=N/2;i++)
        cat[i] = cat[i-1]*(4*i-2)%M*inv1[i+1]%M;
    while(Q--)
    {
        scanf("%lld",&n);
        if(n==1)
        {
            puts("2");
            continue;
        }
        int m=n/2;
        if(n%2==0)
            printf("%lld\n",cat[m]);
        else
            printf("%lld\n",2*cat[m+1]%M);
    }

    return 0;
}

祝大家 AC 愉快！