标签：right frac 闲话 sum 24.7 28 2n binom left

闲话

今天闲话的内容其实已经在前面的闲话里预告了（
下面把 YDRG006G 称作 (?) 题。（这也是内部通称）
6.18：实现了 (?) 题的 std
7.15：确定 (?) 题会出现在熨斗月赛

这题还挺简单的不是吗（
至少场上有个组合意义大神（handle：shijiuwan）推出了只用组合数的式子：

\[\left(\dbinom{2n}n-\dbinom{2n}{n+1}\right)\dbinom nk+\sum_{x=1}^n\sum_{y=0}^{x-1}\sum_{i=1}^{\min(k,x)}\dbinom{x-1}{i-1}\dbinom{n-y}{k-i}\left(\dbinom{x+y-1}{x-1}-\dbinom{x+y-1}x\right)\left(\dbinom{2n-x-y}{n-y}-\dbinom{2n-x-y}{n-y+1}\right) \]

呃呃。有没有数学大神帮我看看这个还有救吗（

推歌：七月狭缝 by 负二价- feat. 言和
仙品 /qdqd

放下成箱的行李
在六月常驻的雨
捡起泛黄的信笺
我梦见
物质 / 是脉搏的化石
生命 / 是传承的歌谣

祛魅：云斗新比赛的括号序列题怎么做？

本题来自我和 jijidawang。我只把我的部分放在下面，想要全部题解的可以去找 jjdw 要 pdf。

合法括号序列的定义：

1. () 是合法括号序列；
2. 若 A 是合法括号序列，则 (A) 也是合法括号序列；
3. 若 A，B 都是合法括号序列，则 AB 也是合法括号序列；
4. 除此之外的所有括号序列均不是合法括号序列。

(?) 题

一个字符集为 \(\{\)(, ?, )\(\}\) 的序列是好的，当且仅当存在一种方案，使得把每个 ? 替换为 ( 或 ) 后得到的序列是合法括号序列。

现在给定 \(n\)，你需要对每个 \(1\le k \le n\) 计数长度为 \(2n\)，恰包含 \(k\) 个 ? 的好序列。答案对 \(10^9 + 3579\)（一个质数，非 ntt 模数）取模。

\(1\le n\le 10^7\)，时间限制 \(10s\)。

常数真的很大（
specify 不是我做的，我只会 analyze。

jjdw 声称，通过 [数据删除] 我们可以知道答案即为

\[[s^kt^{2n}] \frac{\left(1-\sqrt{1-4(1+s)t^2}\right)\left(1-\sqrt{1-4(1+s)t^2}-4(1+s)t^2\right)}{2(1+s)^2t^2\left(1-\sqrt{1-4(1+s)t^2}-2(2+s)t^2\right)} \]

你相信这个式子可以 \(O(n)\) 求一行吗？

可能并不相信！但是接下来你会慢慢相信我的

标签：right,frac,闲话,sum,24.7,28,2n,binom,left
From： https://www.cnblogs.com/joke3579/p/-/chitchat240728