【FCS NOI2018】福建省冬摸鱼笔记 day6【FJOI 2018】福建省选混分滚蛋记 day1

时间:2021-06-30 13:51:18

记录一下day6发生的事情吧。

7:30

到达附中求索碑,被人膜,掉RP。

7:50

进考场,6楼的最后一排的最左边的位置,世界上最角落的地方,没有任何想法。

发现电脑时间和别人不一样,赶快调了一下。

8:00

等待发题。

8:03

题发了,为什么要迟发呢。=)

8:05-9:30

冥思苦想T1什么鬼东西。中间看了看T2T3是啥。

9:30-10:30

对T3的水震惊之余,把T3切掉了,顺便在准考证背面写了题解,准备给同学看看,以便带出去交流。

10:50-12:00

思考T2骗分,T2又是DNA序列,思考为什么FJ不建一个全国基因研究库,就开在FCS里面,专门研究不相交DNA序列反转和两个DNA的最近公共祖先的长度呢?

最终还是输出了-1。233333

12:00-13:00

和@qrc交流T3,和其他人讲T3怎么做,期盼自己能ACT3。

13:00-18:30

机房划水,TR灾厄坑有了很大的进展,见识了克苏鲁之眼的狂暴形态。(???)

看了成绩,稳稳110,和nealchen并列FJ No.12,非常的舒服。


说说题解吧,也只会T3了

【T3】

题意:有n个城市,每个城市都有p个出入口,第\(i\)个城市的第\(j\)个出口有\(U_{i,j}\)条路径,入口有\(V_{i,j}\)条路径,从一个城市的第\(j\)出口出去,也要在另一个城市的第\(j\)入口进入才行。

那么,请你求出经过不超过k条路径的,从S旅行到T的方案数吧,虽然城市的图是一样的,但是有多组询问哦。

数据范围:\(1\leq n\leq 1000,1\leq p\leq 20,0\leq k\leq 10^{18}\)。

题解:观察到图的邻接矩阵是乘积的形式:\(A_{i,j}=\sum_{k=1}^{p}U_{i,p}\cdot V_{j,p}=\sum_{k=1}^{p}U_{i,p}\cdot V^{T}_{p,j}=U\cdot V^T\),准确的说,是矩阵乘积的形式!

这给接下来的解题提供了提示。

那么我们要求出\(Sum=A^0+A^1+\cdots+A^k\),准确的说,要求出\(Sum_{S,T}\),这里的\(Sum\)是一个矩阵哦。

如果直接计算,矩阵乘法都会TLE。

那么我们化简:

\(Sum=I+U\cdot V^T+U\cdot V^T\cdot U\cdot V^T+\cdots+(U\times V^T)^k\)

\(Sum=I+U\cdot(I+V^T\cdot U+(V^T\cdot U)^2+\cdots+(V^T\cdot U)^{k-1})\cdot V^T\)

恐怖的式子,对吧。但是我们完成了很重要的一步,注意到了吗:\(V^T\cdot U\)是一个\(p\times p\)的矩阵,这说明了矩阵乘法变得更快了!

用以往的技巧,构造\(2p\times 2p\)的矩阵,可以记录前缀和。

把这个矩阵的1,2,4,8,16...次幂记录下来,就可以直接快速求得任意次幂了。注意加上稀疏矩阵优化。

最终,前乘\(U\),后乘\(V^T\),再加上单位矩阵,就得到答案。

最后的小优化:因为求得是\(Sum_{S,T}\),只要一个元素,可以更快求出来,不用求出整个\(Sum\)。

那么这题就算做完了。