先补一波 CTS2019。

全数数阵容有点震撼。

D1T1 \(\color{Gold}\bigstar\)

感觉数数的方向错了就寄了。

发现一个不可做的式子应该从头开始换方向考虑。

题目保证 \(k\) 比较小，但好像没什么用，还是需要考虑容斥，设 \(f_i\) 表示钦定 \(i\) 个极大点的方案数，那么答案就是：

然后就去求 \(f_i\)。

我一开始的想法是考虑枚举这 \(i\) 个极大点的编号，然后方案数就是 \(i\) 个下降幂乘起来的形式，然后可以发现 \(i\) 个点间是不影响的，但是需要满足一个偏序关系，不太可做。

换个角度，考虑一层一层去放。

\(i\) 个极大点无论怎么放，其影响的格子总数都是一样的，也就是 \(nml-(n-i)(m-i)(l-i)\)，记 \(s_i=(n-i)(m-i)(l-i)\)。

与这 \(i\) 个点无关的可以乱放，方案数 \(\binom{s_0}{s_k}s_k!\)。

确定这 \(i\) 个点的位置，方案数 \(n^{\underline i}m^{\underline i}l^{\underline i}\)。

然后放影响的，剩余的 \(s_0-s_k\) 个数中，最大的数一定是极大点，把它选出来，然后再选一些点放在它影响的范围内，然后剩余的点就再拿出最大的点作为极大点。

考虑影响的范围，编号比你小的极大点范围内的点显然不需要考虑，画个图，第 \(j\) 层的个数为 $s_{k-j}-s_{k-j+1} $。

因此第 \(j\) 层的方案数为 \((s_0-s_{k-j+1}-1)^{\underline{s_{k-j}-s_{k-j+1}-1}}=\frac{(s_0-s_{k-j+1}-1)!}{s_0-s_{k-j}}\)。

全部乘起来：

线性逆元，复杂度 \(O(Tn)\)。

D1T2 \(\color{blue}\bigstar\)

不是很难的题。

一种方案是否满足条件，放在值域上考虑，如果 \(i\) 选了 \(a_i\) 个，那么只和 \(a_i\) 有多少个奇数有关。

枚举一下有多少个奇数，可以得到式子：

这个东西不太好做，因为后面的两个东西都需要展开。

考虑二项式反演一下，把其中一个变成 \(e^x\)。

设 \(f_i\) 表示钦定 \(i\) 个选奇数之后的方案数，可以得到：

最右边那个可以预处理成一个 \(g_{i-j}\)，然后卷积即可。

最后二项式反演回来，复杂度 \(O(n\log n)\)。

D1T3

提交答案，扔了。

D2T1

计算几何，先咕。

D2T2 \(\color{red}\bigstar\)

好高妙的题。

我的想法是先考虑建一个 trie 树，那么一个串字典序比 \(s\) 小是好判断的，然后循环同构算一下，那么在重复的方案里只能选一个去统计，然后不会了。

第一步转化是考虑容斥，换成每个子串都大于等于 \(s\)。

相当于在 kmp 上匹配，考虑一个点的出边，那么要么前往另一个点，要么前往 \(0\)，因为不能走字典序小的边。

设 \(P(x)\) 表示串 \(x\) 匹配到的节点。

\(P(T^{\infty})=P(T^{\infty}+T)\)，所以在后面加个 \(T\) ，在 kmp 上的匹配是一个环。

然后考虑如果 \(P(N)=P(N+T)=P(N+T^{\infty})\)，那么和 \(N\) 匹配的后缀肯定 \(T^{\infty}\) 里也有，所以 \(P(T^{\infty})=P(N)\)。

因此找到一个 kmp 上的节点，以及一个串 \(T\)，满足绕成一个环就对应一个方案。

出边只有两种，到一个点，到 \(0\)。

因此枚举几步之后到达 \(0\)，如果完全没有经过 \(0\) 方案数就是 \(1\)。

复杂度 \(O(nm)\)。

D2T3 \(\color{blue}\bigstar\)

全场最简单的题了吧。

先考虑如果是 \(T_1<T_2<T_3<T_4...\) 咋做。

选 \(1\) 的时候，把后面的看成是一个整体，概率是 \(\frac{W_1}{\sum_{i=1}^n W_i}\)，总概率就是每一个除以后缀和乘起来。

那么外向树，自然就是 \(\prod \frac{W_i}{siz_i}\)，\(siz_i\) 表示 \(W_i\) 的子树和。

会有内向的边，直接容斥，要么把这条边删掉，要么把它变成外向边，然后乘上容斥系数加起来。

背包，\(f_{i,j}\) 表示 \(i\) 子树内的子树大小为 \(j\) 的总和，直接做即可。

复杂度 \(O(n^2)\)。

学习了一下斯特林反演。

不过好像没啥用啊。。。

bzoj4671

这个题，先想到了直接状压然后容斥之类的东西，但是很难做，因为边之间会相互影响。

考虑直接枚举最后的图连通块划分，这个是个贝尔数，很小，然后把中间的边全部断掉，这个可以线性基算。

然后咋算答案啊，先设一个 \(f_i\) 表示钦定 \(i\) 个连通块的方案数，\(g_i\) 表示恰好为 \(i\) 个连通块的方案数，得到：

然后这个可以 \(O(n^2)\) 暴力反演，没了。

CF1677E *2900 \(\color{blue}\bigstar\)

枚举 \(p_i,p_j\)，对数是 \(O(n\log n)\) 的。

观察每一对数造成贡献的区间，会发现是左端点是 \((L_i,l]\) ，右端点是 \([r,R_i)\) 的所有区间。

\(L_i,R_i\) 表示 \(i\) 这个数左边、右边离他最近的比他大的数，这个可以单调栈。

那么这个贡献就是一个矩形，问题变成矩形覆盖，矩形求和。

不可做。

那么观察一下矩阵的特殊性质，覆盖不好做，但是我们会做矩阵加，因此只需要把矩阵拆成不相交的就好了。

容易发现对于每个 \(p_i\times p_j\) 不同的矩形一定不会相交，因为区间最大值只有一个。

那么相当于只需要处理内部，那么把所有 \([l,r]\) 离线下来，就可以转化为若干个区间满足不交了。

然后矩形加，矩形和，这个可以直接历史和线段树即可，这个跑的比 cdq 快很多。

复杂度 \(O(n\log^2 n+q\log n)\)。

后面那个东西也可以离线下来树状数组，不过不太会。

CF1817C *2400 \(\color{Gold}\bigstar\)

赛时感觉和平常做题很不一样，很没有脑子，玉玉了。

给你点值，显然就是来插值的。

一开始有个暴力做法，就是插值出系数，然后把 \(x+s\) 带入展开，然后解一个方程。

然后没继续想，输麻了，后面一直以为是什么乱搞。

结果很简单啊，展开只需要展开到 \(x^{d-1}\) 的系数就好了，因为这个的式子和 \(s\) 有关，就可以解出来，由于题目保证有解，因此不需要考虑后面每一位是否合法了。

反正就列一下插值系数的式子就做完了。