矩阵乘法

一道让我做得相当高兴的题目。

原题链接 (这是付费比赛。)

题意简述

给定长度为 nn 的序列 aa。定义函数 f(S)=TSF2(sTs)f(S)=\sum\limits_{T\subseteq S} F^2(\sum_{s\in T} s),也即“对于 SS 的所有子集,求 F(子集所有元素之和)的平方F(\text{子集所有元素之和})\text{的平方} 之和”。其中 F(x)F(x) 为斐波那契数列的第 xx 项。有F(0)=0,F(1)=1,F(x)=F(x1)+F(x2)(x>1)F(0)=0, F(1)=1, F(x)=F(x-1)+F(x-2) (x > 1)

你需要支持以下操作,操作总数为 mm

1 x y:将 axa_x 修改为 yy

2 l r:输出 i=lrj=irf({ai,ai+1,,aj})\sum\limits_{i=l}^{r}\sum\limits_{j=i}^{r}f(\{a_i, a_{i+1}, \cdots, a_{j}\}),对 998244353998244353 取模。

数据范围:对于 50%\text{50\%} 的数据,有 n,m100n,m\leq 100;对于 70%\text{70\%} 的数据,有 n,m1000n,m\leq 1000;对于 100%\text{100\%} 的数据,有 n,m105,ai105n,m\leq 10^5, a_i \leq 10^5

(更多…)

More
  • 2022年6月20日

昨晚参与AtCoder ABC 236时认为G题似乎可做,直到看到数据范围才发现事情没有那么简单

由于最近学习离线数据结构,又见识过一道题意接近的题目,故想到整体二分,二分每一个节点第一次能恰好经过LL条边到达的时间,然后考虑DP求解。设计状态f(i,x)f(i, x)表示在该图上经过恰好ii次转移能否到达点xx。但很快发现每一次二分时均要重新在图上运行DP,时间复杂度无法承受。况且DP递推转移的次数LL高达10910^9,甚至不可能是线性的复杂度。

今天查看题解,发现有几个重要的,从未考虑过的trick:

  1. 既然要求能够经恰好LL次转移到达的最早的时间点,则我们将每条边的边权ww设为其加入图中的时间,则可以转化成恰有LL条边的最小瓶颈路
  2. 发现LL很大,所以考虑通过矩阵乘法加速递推,也即所谓倍增优化DP的一种。

(更多…)

More
  • 2022年1月24日