CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
[[http://wiki.buaaacm.com/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95|back]]

====== 2020/08/22--2020/08/28 周报 ======

===== 团队训练 =====

===== 姜一凡 =====

==== 专题 ====

[[..:qgjyf2001:虚树]]

==== 比赛 ====

==== 题目 ====

===== 蒋贤蒙 =====

==== 专题 ====

[[..:jxm2001:二项式反演]]

[[..:jxm2001:斯特林数]]

[[..:jxm2001:多项式_4|多项式 4]]

[[..:jxm2001:字符串_1|字符串 1]]

==== 比赛 ====

无

==== 题目 ====

无

===== 王赵安 =====

==== 专题 ====

[[..:lgwza:Splay|Splay]]

[[..:lgwza:2-SAT|2-SAT]]
==== 比赛 ====

==== 题目 ====

===== 本周推荐 =====

==== 姜一凡 ====

[[https://www.luogu.com.cn/problem/P2495|洛谷p2495]]

=== 题目大意 ===

给定一棵树， $m$ 个询问，每次询问 $k$ 个点均不与 $1$ 号点相连的最小代价和。

=== 题解 ===

$dp[now]$ 为now节点及下属节点的最小代价和，则 $dp[now]=\left\{ \begin{aligned}edge[now][fa].w,target[now]=true \\ \sum dp[v],now=1\\min(\sum dp[v],edge[now][fa].w),others\end{aligned} \right.$ 。使用虚树求解。

==== 蒋贤蒙 ====

[[https://www.luogu.com.cn/problem/P5293|洛谷p5293]]

=== 标签 ===

FFT，单位根反演，数学

=== 题意 ===

给定一个二维 $[L+1]\times n$ 的空间，其中 $(u_1,v_1)\to (u_2,v_2)$ 有 $w_{v_1,v_2}$ 条重边。

假设起点为 $(0,x)$，终点为 $(\ast,y)$($\ast$ 为任意值)，路径长度 $m$ 定义为路径的边数。

对每个 $0\le t\lt k$，求满足所有 $m\equiv t\pmod k$ 且横坐标单增的路径数模 $p$ 意义下的值。

数据保证 $p$ 为素数，$10^8\le p\le 2^{30},k\mid p-1,1\le k\lt 65536,1\le n\le 3,L\le 10^9$。

=== 题解 ===

假设 $f_{a,b}$ 表示 $m=a$ 且 $y=b$ 的路径数，$g_{a,b}$ 表示将空间的 $X$ 维消去后 $m=a$ 且 $y=b$ 的路径数。

于是有状态转移方程

$$g_{a,b}=\sum_{i=1}^n g_{a-1,i}w_{i,b}\text{ },\text{ }f_{a,b}={L\choose a}g_{a,b}$$

设矩阵

$$W=\begin{bmatrix}w_{1,1} & \cdots & w_{1,n} \\
\vdots &\ddots & \vdots \\
w_{n,1} &\cdots & w_{n,n}\end{bmatrix}$$

设 $G_i=(g_{i,1}\cdots g_{i,n})$，于是有 $G_i=G_0W^i$。

考虑单位根反演，设 $w_k\equiv g^{\frac {p-1}k}\pmod p,g$ 为 $p$ 的原根，有

$$
\begin{equation}\begin{split} 
\text{ans}_t&=\sum_{i=0}^Lf_{i,y}[i\bmod k=t]\\ 
&=\frac 1k\sum_{i=0}^Lf_{i,y}\sum_{j=0}^{k-1}w_k^{(i-t)j}\\ 
&=\frac 1k\sum_{j=0}^{k-1}w_k^{-tj}\sum_{i=0}^L f_{i,y}w_k^{ij}
\end{split}\end{equation}
$$

根据二项式定理，有

$$\sum_{i=0}^L w_k^{ij}(f_{i,1}\cdots f_{i,n})=\sum_{i=0}^L w_k^{ij}{L\choose i}(g_{i,1}\cdots g_{i,n})=G_0\sum_{i=0}^L {L\choose i}\left(w_k^jW\right)^i=G_0\left(w_k^jW+I\right)^L$$

于是根据矩阵快速幂可以 $O(kn^3\log L)$ 计算出所有 $h_j=\sum_{i=0}^L f_{i,y}w_k^{ij}(0\le j\lt k)$。

于是有

$$\text{ans}_t=\frac 1k\sum_{i=0}^{k-1}w_k^{-ti}h_i$$

发现上式就是 $\text{Bluestein's Algotithm}$ 的 $\text{IDFT}$ 过程，直接求解时间复杂度 $O(k\log k)$。

总时间复杂度 $O(kn^3\log L)$，主要用于计算矩阵快速幂。

=== 评价 ===

一道有一定思维量的循环卷积题。

==== 王赵安 ====

**2018-2019 ACM-ICPC Asia Seoul Regional K [[http://codeforces.com/gym/101987|TV Show Game]]**

**标签**

2-SAT，tarjan 求强连通分量(SCC)，缩点

**题意**

有 $k(k>3)$ 盏灯，每盏灯是红色或者蓝色，但是初始的时候不知道灯的颜色。有 $n$ 个人，每个人选择 3 盏灯并猜灯的颜色。一个人猜对两盏灯或以上的颜色就可以获得奖品。判断是否存在一个灯的着色方案使得每个人都能领奖，若有则输出一种灯的着色方案。这道题在判断是否有方案的基础上，在有方案时还要输出一个可行解。

**题解**

首先连边建图，然后用 tarjan 求强连通分量，若出现一组的两个元素都出现在同一个强连通分量中，则无解，反之有解。如果要输出 2-SAT 问题的一个可行解，只需要在 tarjan 缩点后所得的 DAG 上自底向上地进行选择和删除。具体实现的时候，可以通过构造 DAG 的反图后在反图上进行拓扑排序实现；也可以根据 tarjan 缩点后，所属连通块编号越小，节点越靠近叶子节点这一性质，优先对所属连通块编号小的节点进行选择。

**评价**

一道对 2-SAT 问题的理解很有帮助的题。
CVBB ACM Team

用户工具

站点工具

页面工具
