线性代数

恕我语文不好,实在不晓得用何种词汇来描述看到下文的感受:

此比赛为正常的提高组难度,甚至可以用来作为普及组模拟赛。 请选手 AK 后不要大声喧哗,以免影响他人 AK。

尤其是这套题的出题人是张隽铠的情况下。当然,OI 圈风气本就如此,我也不好过多评价。No comment.

T1 还算顺利,半小时左右搞定。T2 是大分类讨论,足够恶心人,但好在有相当可观的可以通过暴力与观察拿到的部分分。T3 猜测与线性基相关,但没有相应知识储备,暴力跑路。

T4 就……反正出题人开心就好。到现在都没人改出来。

一句话题解

A – 序列

依次往某个子序列中添加元素。则添加的元素必然成为新的最大值/最小值之一,否则违背题意。

于是枚举子序列首元素,将以其开头的严格上升子序列数与严格下降子序列数相乘即可。使用树状数组转移即可。复杂度 O(nlogn)\operatorname{O}(n \log n)(更多…)

More
  • 2022年10月19日

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

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

题意简述

给定长度为 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 取模。

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

(更多…)

More
  • 2022年6月20日

考虑这个排列是怎样生成的。转述一下题意,可以发现,popcount(PiPi+1mod2n)=K\operatorname{popcount}(P_i \oplus P_{i+1 \mod {2^n}})=K,也即全集msk=2N1\text{msk}=2^N-1的一个大小为KK的子集。

由于这是一个环排列,我们不妨令P0=0P_0=0。这样一来,Pi=j=1iSj,Sj=KP_i=\operatorname{\bigoplus}\limits_{j=1}^{i}S_j, |S_j|=K。结合上文可知,这是一个相邻元素二进制位恰相差KK位的格雷码问题。有K=1K=1时,满足条件的SjS_j恰有NN个,也就是NN位格雷码。

考虑推广。我们发现,如果按照类格雷码的方式生成排列,则所有的SjS_j应构成异或空间,其大小应当恰为2N2^N,并且由线性空间知识可以得到,该线性空间的(基的大小)应当恰为NN。这恰好符合NN位格雷码的构造。因此,只要满足上述条件,就一定能够生成符合题意的排列。

可以证明,除了2K(K=NN>1)2\mid K \lor (K=N \land N>1)以外,总是有满足条件的线性空间生成的。

下述解法的时间复杂度O((NK)+2N)\operatorname{O}\left(\dbinom{N}{K}+2^N\right)(更多…)

More
  • 2022年4月11日