[Luogu]P7044 「MCOI-03」括号
本文最后更新于 82 天前,其中的信息可能已经有所发展或是发生改变。

Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。
原文链接:https://www.codein.icu/lp7044/

题解

首先考虑 $0$ 级偏值如何求解。

首先求出 $f(1,i)$ 即 $[1,i]$ 的最少操作次数,可以用一个栈一路模拟过去。

接下来考虑移动左端点,答案会如何改变。

如果左端点移动后,去掉了一个 ‘)’,那么 $f$ 都减少 $1$,因为开头的 ‘)’ 只能产生贡献。

如果左端点移动后,去掉了一个 ‘(‘,那么情况就有些复杂了。

  • 原本这个 ‘(‘ 是多余的,那么去掉后 $f$ 会减少 $1$
  • 原本这个 ‘(‘ 是有用的,那么去掉后 $f$ 会增加 $1$

如何划分有没有用呢?在原串中,与它匹配的右括号位置为分界线,往左它是多余的,往右它是有用的。

那么在一开始求出初始串的 $f$ 时,顺便求出每个左括号匹配的右括号的位置。

这样就可以计算出每次移动左端点后,$f$ 数组的变化。

如果是 $0$ 级偏值,这已经足够了,在变化时维护和即可。

考虑加上偏值之后,实质上就是一个串的贡献被多次统计。
被统计多少次呢?考虑一个串会怎样被当成子串计入贡献。

$k$ 级偏值,那么它作为 $k$ 级子串的次数就是被统计的次数。

对于 $f(l,r)$,包含它为子串的原串的左右端点可以在 $[1,l]$ 与 $[r,n]$ 中选择。

而 $k$ 级,相当于左端点向左移动了 $k – 1$ 次,并且 $k – 1$ 次后一定移动到 $1$.
而左端点一共需要移动 $l – 1$ 步,在 $k – 1$ 次中完成。
而由于可以不动,可以转化成:将 $l – 1$ 个小球放入 $k – 1$ 个盒子中,盒子可空的方案数。

由隔板法知,方案数为 $l – 1 + k – 1 \choose k – 1$.

右端点同理为 $n – r + k – 1 \choose k – 1$

那么 $f(l,r)$ 对答案的贡献就是 $f(l,r) \times {{l – 1 + k – 1} \choose {k – 1}} \times {{n – r + k – 1} \choose {k – 1}}$

将这个贡献记为 $T(l,r)$,考虑左端点变化时, $T(l,r)$ 相应地如何变化。

发现其实在 $T(l,r) = f(l,r) \times {{l – 1 + k – 1} \choose {k – 1}} \times {{n – r + k – 1} \choose {k – 1}}$ 的过程中,${{n – r + k – 1} \choose {k – 1}}$ 是不改变的。
而 ${{l – 1 + k – 1} \choose {k – 1}}$ 仅与左端点有关,而 $f(l,r)$ 变化可以计算得出。

调换一下式子顺序:

$T(l,r) = {{l – 1 + k – 1} \choose {k – 1}} \times f(l,r) \times {{n – r + k – 1} \choose {k – 1}}$

需要统计的是 $\sum T(l,i) = {{l – 1 + k – 1} \choose {k – 1}} \times \sum f(l,i) \times {{n – i + k – 1} \choose {k – 1}}$

可以预处理出每个右端点对应的 ${{n – i + k – 1} \choose {k – 1}}$,然后做一个前缀和,就能在区间修改 $f(l,i)$ 时更新贡献。

然后动态修改 $f(i)$ 来使 $f(1,i)$ 变成 $f(l,i)$,由于每次只修改向后的区间,可以通过差分数组直接实现。

枚举左端点,更新答案,累加贡献。

代码

#include <algorithm>
#include <cstdio>
#include <ctype.h>
using namespace std;
const int mod = 998244353;
const int maxn = 2e6 + 100;
const int bufSize = 1e6;
inline char nc()
{
#ifdef DEBUG
    return getchar();
#endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
T read(T& r)
{
    static char c;
    r = 0;
    for (c = nc(); !isdigit(c); c = nc());
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r;
}
void read(char* s)
{
    static char c;
    for (c = nc(); c != '(' && c != ')'; c = nc());
    for (; c == '(' || c == ')'; c = nc()) *s++ = c;
    *s = '\0';
}
int n, k;
char s[maxn];
inline int add(int x, int y)
{
    int res = x + y;
    return res >= mod ? res - mod : res;
}
inline int mul(int x, int y) { return 1ll * x * y % mod; }
int prod[maxn], prodinv[maxn], inv[maxn], f[maxn];
inline int C(int n, int m) { return mul(prod[n], mul(prodinv[n - m], prodinv[m])); }
void init()
{
    read(n), read(k), read(s + 1);
    prod[0] = prodinv[0] = 1, inv[1] = 1;
    for (int i = 2; i <= n + k; ++i) inv[i] = mul(inv[mod % i], mod - mod / i);
    for (int i = 1; i <= n + k; ++i) prod[i] = mul(prod[i - 1], i), prodinv[i] = mul(prodinv[i - 1], inv[i]);
}
int st[maxn], top, match[maxn];
int rval[maxn], rsum[maxn], d[maxn];
inline int getrange(int l, int r) { return add(rsum[r], mod - rsum[l - 1]); }
int main()
{
    init();
    for (int i = 1; i <= n; ++i)
    {
        if (s[i] == '(') st[++top] = i;
        else
        {
            if (top && s[st[top]] == '(') match[st[top--]] = i;
            else st[++top] = i;
        }
        f[i] = top;
    }
    if (k == 0) { printf("%d\n", f[n]); return 0; }
    for (int i = 1; i <= n; ++i) rval[i] = C(n - i + k - 1, k - 1), rsum[i] = add(rsum[i - 1], rval[i]);
    int sum = 0, res = 0;
    for (int i = 1; i <= n; ++i) sum = add(sum, mul(f[i], rval[i]));
    for (int l = 1; l <= n; ++l)
    {
        d[l] = add(d[l], d[l - 1]);
        f[l] = add(f[l], d[l]);
        int Ltimes = C(l - 1 + k - 1, k - 1);
        res = add(res, mul(Ltimes, sum));
        sum = add(sum, mod - mul(f[l], rval[l]));
        if (s[l] == ')')
        {
            d[l + 1] = add(d[l + 1], mod - 1);
            sum = add(sum, mod - getrange(l + 1, n));
        }
        else
        {
            if (match[l] == 0)
            {
                //no match, all decrease
                d[l + 1] = add(d[l + 1], mod - 1);
                sum = add(sum, mod - getrange(l + 1, n));
            }
            else
            {
                // [l + 1, match[l] - 1] decrease, [match[l], n] increase
                if (match[l] - 1 >= l + 1)
                {
                    d[l + 1] = add(d[l + 1], mod - 1);
                    d[match[l]] = add(d[match[l]], 1);
                    sum = add(sum, mod - getrange(l + 1, match[l] - 1));
                }
                if (match[l] <= n)
                {
                    d[match[l]] = add(d[match[l]], 1);
                    sum = add(sum, getrange(match[l], n));
                }
            }
        }
    }
    printf("%d\n", res);
    return 0;
}
本文标题:[Luogu]P7044 「MCOI-03」括号
本文作者:Clouder
本文链接: https://www.codein.icu/lp7044/
转载请标明。
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇