【CF785D】Anton and School – 2

这个题是伟大的红太阳学长出给我和刘神仙做的题,当时考场只想到了60分奇怪dp,考完听学长一讲才恍然大悟
首先考虑最暴力的dp
\(\sum_{i=1}^{n}\sum_{j=1}^{min(a_i-1, b_i-1)}C_{a_i}^{j}C_{b_i-1}^{j}\)
ai是表示目前左括号个数,bi右括号,这个显然n^2,过不掉
那么,我们是不是可以化简这个式子呢
\(\sum_{j=1}^{min(a_i-1, b_i-1)}C_{a_i}^{j}C_{b_i-1}^{j}=\sum_{j=1}^{min(a_i-1, b_i-1)}C_{a_i}^{a_i-j}C_{b_i-1}^{j}\)
这个式子开始变得和原来的式子不一样了,我们开始从这个式子非公式角度的去讨论它,这个式子就表示,在ai种物品里面选取ai-j种,在bi-1种物品里选择j种(我们保证i这位一定被选择)
那么这俩式子一乘,再求个和,实际上就等于\(C_{a_i+b_i-1}^{a_i}\)
这个式子就表示在ai+bi-1种物品里面选择ai个物品的方案数
那么我现在就可以得到这个式子\(\sum_{i=1}^{n}C_{a_i+b_i-1}^{a_i}\),这个东西显然可以递推,时间复杂度O(n)(线性求逆元的时候)

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register long long

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = (x << 1) + (x << 3) + a - '0', a = getchar();
    if(b == 1)
        x *= -1;
}

const int ms = 200010;

const lo mo = 1e9 + 7;

int n, a[ms], b[ms];

bool fl[ms];

lo ans, inv[ms], pre[ms];

char lx;

int main()
{
    while(((lx = getchar()) != '(' && lx != ')')); inv[0] = inv[1] = pre[1] = pre[0] = 1;
    while(lx == '(' || lx == ')')
        fl[++ n] = (lx == '(') ? 0 : 1, a[n] = a[n - 1] + (fl[n] == 0), lx = getchar();
    for(ri i = n; i >= 1; i --)
        b[i] = b[i + 1] + (fl[i] == 1);
    for(ri i = 2; i <= n; i ++)
        inv[i] = inv[i - 1] * i % mo, pre[i] = (mo - mo / i) * pre[mo % i] % mo;
    for(ri i = 1; i <= n; i ++)
        pre[i] = pre[i] * pre[i - 1] % mo;
    for(ri i = 1; i <= n; i ++)
    {
        if(fl[i] == 1)
            continue;
        ans = (ans + inv[a[i] + b[i] - 1] * pre[a[i]] % mo * pre[b[i] - 1] % mo) % mo;
    }
    printf("%lld\n", ans); 
} 

发表评论

电子邮件地址不会被公开。 必填项已用*标注