2020 CCPC Wannafly Winter Camp Day6¶

A¶

题意¶

给定序列 $a_1,a_2,\cdots,a_n$，求下式的值： $$ \left(\sum_{i=1}^n \sum_{j=1}^n 2^{a_ia_j}\right) \bmod {998244353} $$ ($1 \le n \le 10^5$，$0 \le a_i \le 10^5$)

题解¶

\[ \begin{aligned} &\sum_{i=1}^n \sum_{j=1}^n 2^{a_ia_j} \newline =& \sum_{i=1}^n \sum_{j=1}^n 2^{\frac{1}{2}\left({(a_i+a_j)}^2-a_i^2-a_j^2\right)} \newline =& \sum_{i=1}^n \sum_{j=1}^n {\sqrt 2}^{{(a_i+a_j)}^2-a_i^2-a_j^2} \newline =& \sum_{i=1}^n \sum_{j=1}^n {\left(\frac{1}{\sqrt 2}\right)}^{a_i^2} {\left(\frac{1}{\sqrt 2}\right)}^{a_j^2} {\sqrt 2}^{{(a_i+a_j)}^2} \newline =& \sum_{a_i+a_j=k} {\left(\frac{1}{\sqrt 2}\right)}^{a_i^2} {\left(\frac{1}{\sqrt 2}\right)}^{a_j^2} {\sqrt 2}^{k^2} \end{aligned} \]

另有：

\[ \sqrt 2 \equiv 116195171 \pmod{998244353} \]

从而可以使用 NTT 求解，设 $A$ 为 $a_i$ 的最大值，复杂度即为 $O(A \log A)$。

D¶

题意¶

求所有满足 $l_i \le i \le r_i$ 的所有不严格递增序列的序列元素之和。($1 \le n \le 50$，$0 \le l_i \le r_i < 2^{60}$)

题解¶

求方案数是经典问题，离散化后设 $f_{i,j}$ 为考虑前 $i$ 个数，最后一个数在 $j$ 这个区间的方案数，转移为：

\[ f_{i,j} = \sum_{k=1}^{j-1}[\forall(k \le l \le i),F(l,j)]\binom{\textit{len}_j+i-k-1}{i-k}\sum_{m=1}^{k-1}f_{i-1,m} \]

其中 $\textit{len}_i$ 表示离散化后第 $i$ 个区间对应的长度，$F(i,j)$ 表示第 $i$ 个数的区间是否包含离散化后的第 $j$ 个区间。上式我们在 dp 过程中逆序枚举 $j$ ，判断当前区间是否合法，并在过程中计算组合数，同时记录 $f_{i,j}$ 的前缀和，就可以在 $O(n^3)$ 的时间内完成。

但本题还需要计算所有方案的序列元素之和，我们可以使用对称的思想：考虑一个在 $[l,r]$ 中选 $k$ 个数使其不严格递增，当第 $i$ 个位置为 $x$ 时的方案数，必然等于第 $k+1-i$ 个位置为 $l+r-x$ 时的方案数，利用对称的思想很容易证明，由于我们求的是所有方案的序列元素之和，我们可以直接让每个元素的值等于 $\dfrac{l+r}{2}$。设 $g_{i,j}$ 为考虑前 $i$ 个数，最后一个数在 $j$ 这个区间的所有方案的序列元素之和，有如下转移：

\[ g_{i,j} = \sum_{k=1}^{j-1}[\forall(k \le l \le i),F(l,j)]\binom{\textit{len}_j+i-k-1}{i-k}\left(\left(\sum_{m=1}^{k-1}g_{i-1,m}\right)+\left(\sum_{m=1}^{k-1}f_{i-1,m}\right)\frac{\textit{sum}_{k,i}}{2}(i-k)\right) \]

其中 $\textit{sum}_{i,j}$ 表示离散化后区间 $[i,j]$ 对应的原区间左右端点之和，$f_{i,j}$ 和 $g_{i,j}$ 可以同时计算，利用上述的转移技巧，总时间复杂度即为 $O(n^3)$。

E¶

题意¶

给定一颗 $n$ 个节点的树，$1$ 号点为根，一开始所有边都是虚边，进行至多 $k$ 次 LCT 中的 access 操作，问最终能得到多少种可能的树。($1 \le n \le 10^4$，$1 \le k \le 500$)

access 操作：选定一个点 $x$，把 $x$ 到根这条路径上的所有点的实儿子边（如果有）全变成虚边，然后把这条路径上的所有边全变成实边。

题解¶

数据范围疯狂暗示 $O(nk)$ 的树形背包。

设 $f_{i,j}$ 表示以 $i$ 为根节点的子树中（不考虑 $i$ 与父亲的边）进行 $j$ 次操作得到的方案数，$g_{x,j,k}$ 表示子树合并过程中考虑了前 $x$ 个子树，选了进行 $j$ 次操作，是否已选一个子树将其作为最后一次操作使得有一条边伸到 $i$，初始有 $g_{0,0,0} = 1$。

如果一颗子树 $x$ 内部没有操作，想让对应的边成为实边必须再对 $x$ 额外操作一次，因此转移如下： $$ \begin{aligned} &f_{x,j}g_{y-1,k,0} \to g_{y,j+k,0} \newline &f_{x,j}g_{y-1,k,0} \to g_{y,j+k+[j=0],1} \newline &f_{x,j}g_{y-1,k,1} \to g_{y,j+k,1} \end{aligned} $$ 最终如果没有选择一个子树将其作为最后一次操作使得有一条边伸到 $i$，那么除非一次操作也没有做过，一定要再对 $i$ 进行一次操作，才可以将其所有儿子边均变为轻边，因此有： $$ \begin{aligned} &g_{s_i,j,0} \to f_{i,j+[j>0]} \newline &g_{s_i,j,1} \to f_{i,j} \end{aligned} $$ 其中 $s_i$ 为 $i$ 的儿子节点数量。最终答案即为 $\sum \limits _{i=0} ^k f_{1,i}$。

F¶

题意¶

给定一张 $n$ 个点的完全无向图，边有黑白之分，求有多少个纯色三角形。($1 \le n \le 5000$)

题解¶

考虑算出有多少对纯黑角，纯白角，异色角，分别设为 $x,y,z$。这里角指的是从一个点伸出去的两条边。

那么一个黑三角形有三个纯黑角，一个白三角形有三个纯白角，一个异色三角形有两个异色角，从而答案即为： $$ \frac{x+y-\frac{z}{2}}{3} $$ 枚举每个点连出去的边，统计分别是什么颜色，可以 $O(1)$ 算出对应角的数量，因此时间复杂度为 $O(n^2)$。

G¶

题意¶

定义一个 $1$ 到 $n$ 的排列 $p_1,p_2,\cdots,p_n$ 的 $f$ 序列如下：

如果存在 $j < i$ 使得 $p_j < p_i$，设 $p_k$ 是所有 $p_j$ 中最大的那一个，则 $f_i = f_k + 1$。
否则，$f_i = 1$。

现在给定一些位置的 $f_i$，其它位置未知，保证给出数据合法，求此条件下字典序最小的排列。($1 \le n \le 100$)

题解¶

首先有 $f_1 = 1$，考虑所有 $f_i=1$ 的位置，设共有 $x$ 个，想让 $p_1$ 尽可能小，最优方案即将 $1,2,\cdots,x$ 逆序填入这些位置，因为如果这些位置不是递减的，必然有一个位置的 $f_i > 1$。

接下来，我们将其余位置的 $f_i$ 减少 $1$（因为其它位置前面都有一个比它小的数，且 $f_i=1$），可以发现此时第一个位置也必然有 $f_i=1$ 或不确定（否则不合法），因此重复上述操作即可确定每一位的值。总时间复杂度为 $O(n^2)$。

I¶

题意¶

给定一个序列 $a_1,a_2,\cdots,a_n$，每次操作可以选择 $2 \le i < n$，令 $a_{i-1},a_i,a_{i+1}$ 都变为 $\max(a_{i-1},a_i,a_{i+1})$，求操作 $1,2,\cdots,n$ 次后所有元素之和的最大值。($3 \le n \le 50$)

题解¶

考虑最终答案一定是数段，每段长度 $\ge 1$ 且值都相同，可以发现获得一个长为 $l$ 的段需要操作 $\left\lfloor\dfrac{l}{2}\right\rfloor$ 次，因此设 $f_{i,j}$ 为前 $i$ 个数操作了 $j$ 次的答案，枚举新增的段数，将段数内所有数的权值设为该段内最大值即可进行转移，总时间复杂度为 $O(n^3)$。

J¶

题意¶

求有多少个 $1$ 到 $n$ 的排列满足所有环长均为 $K$ 的约数。($1 \le n \le 50$，$1 \le K \le 10^{18}$)

题解¶

设 $g_i$ 为 $1$ 到 $i$ 仅有一个环的排列数，枚举 $1$ 所在的环，利用补集转化，有： $$ g_i=i!-\sum_{j=1}^{i-1}g_{j}\binom{i-1}{j-1}(i-j)! $$ 设 $f_i$ 为满足所有环长均为 $K$ 的约数的 $1$ 到 $i$ 的排列数，同样枚举 $1$ 所在的环，有： $$ f_i=\sum_{j=1}^i[K \bmod j = 0]g_j\binom{i-1}{j-1}f_{i-j} $$ 总时间复杂度为 $O(n^2)$。