WGSZ-NOIP2018 Day1

WGSZ-NOIP2018 Day1

T1.Extract

题解 :

我们首先\(O(n)\)处理出括号匹配, 然后递归处理每一个中括号和大括号

不要想得太麻烦了

但是我很傻逼了, 打的\(O(n^2)\)的括号匹配, 由于数据不强, 我还是\(A\)掉了

T2.Class

题解 :

我们首先考虑一个显然的暴力\(DP\)

\(f_{i,j}\)表示前\(i\)个教室容纳了\(j\)个人的方案数

转移显然有 \[ f_{i,j}=\sum_k f_{i - 1, k} \cdot \binom{n - k}{j - k} \] 这个暴力\(DP\)复杂度是\(O(n^2 \cdot m)\)

但是如果转移没有那么丑, 并且加上各种特殊性质送的分, 大概可以获得\(80\)分的好成绩

考虑优化一下

我们转换一下\(DP\)式子所统计的东西

实际上题目就是让我们统计一下这个式子 \[ ans = \sum \frac{n!}{\prod b_i}[\forall b_i \ge a_i] \] 我们可以先不管\(n!\)这个东西可以最后在乘回去

那我们设 \[ f_{i,j} = \sum \frac{1}{\prod b_i} \] 那么转移变成了 \[ f_{i,j} = \sum _ k f_{i - 1, k} \cdot \frac{1}{(j - k)!} \] 然后我们发现这\(TM\)不就是一个卷积吗

然后我们可以\(NTT\)一发题面中的998244353不就是明示NTT吗?滑稽

复杂度变成了\(O(m \cdot nlogn)\)

但是由于出题人太毒瘤了, 这个东西还是只有\(80\)

我们再考虑一个东西, 当两个教室的限制\(a_i\)相同时, 我们可以合并在一起快速幂一发

又因为当\(\sum a_i>n\)时答案就是\(0\)

所以\(\sum a_i \le n\), 所以不同的\(a_i\)只有\(\sqrt n\)个, 然后相同的直接都合并在一起处理就好了

最终复杂度为\(O(n \sqrt n log^2n)\)

可以获得\(100\)分的好成绩

最后值得注意的是\(NTT和FFT\)都是循环卷积, 如果不把\(N\)以后的项数清零, 在膜意义下是会影响到前几位的

这个以后要注意

T3.Hack

出题人刚刚做完一道经典分治题平面最近点对

但是他觉得某谷的数据太水了, 决定来\(Hack\)某谷上的各个假的题解

于是他想让我们来出出\(Hack\)数据

假装大家都会咕咕咕