专栏文章

被虐哭的超级题单记

666xyyd
生活·游记参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miodt2ce
此快照首次捕获于
2025/12/02 17:34
3 个月前
此快照最后确认于
2025/12/02 17:34
3 个月前
查看原文
在8.13时，为了缩减手打题目的负担，先放个神秘代码镇楼。
CPP
#include<iostream>
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	string s;
	while(cin >> s){
		cout << "[" << s << "](";
		if(s[0]=='C' || s[0]=='P'){
			cout << "https://www.luogu.com.cn/problem/" << s;
		} else if(s[0]=='q'){
			cout << "https://qoj.ac/problem/" << string(s.begin()+3,s.end());
		} else if(s[0]=='u'){
			cout << "https://uoj.ac/problem/" << string(s.begin()+3,s.end());
		}
		cout << ")\n"; 
	}
	return 0;
}

Day 1

8.11，非常好的日期。
A. CF1854A2
yq在这里卡了两个小时，过于神秘。死因是yq尝试在实际操作之前就判断做前缀和还是后缀和更优。
B. qoj9479
打表找规律，但是yq打表打错了，对着错误的表找不到序列。
自己写矩阵乘法，错了；写了正确的矩阵乘法（抄的之前板子），又和之前的序列对不上（到这里yq才发现听完课过后手推的式子假了），幸亏xza路过指出。
C. qoj7782
把每次询问中的数划分为 B=gcd⁡(bi)B=\gcd(b_i) 一块，显然可以想到，但是yq想不到/kk。
有一个结论，统计 f(i)=∑k=lr[k%B=i]aif(i)=\sum_{k=l}^{r}[k\%B=i]a_i，那么答案为 Yes 当且仅当所有 f(i)f(i) 均相等（可以通过构造证明）。
可是怎么维护呢？等下根号分治是什么？啊这道题能用根号分治做吗？这下得要好好学学了qwq。
D. uoj841
现在交互题也这么神秘了吗？……
考虑作为答案的直径的两个端点如何变化。如果区间 (l,r)(l,r) 的直径是 (L,R)(L,R)，那么加入点 r+1r+1 后直径只有三种变化：(L,R),(L,r+1),(R,r+1)(L,R),(L,r+1),(R,r+1)。然后分类讨论。发现 r+1r+1 的加入对一定的左端点都会统一做修改，暴力条即可。
组题人正在试图用势能分析法向台下证明这玩意的均摊询问次数是 O(n+6n+n)=O(8n)O(n+6n+n)=O(8n)，然而没有人听懂……
还有神秘结论（要是我听错了搞了个假结论出来就好笑了）：如果 (l,r)(l,r) 中有两个点 (x,y)(x,y) 且直径端点是 L,RL,R，那么如果加入的 r+1r+1 是区间直径的话一定是 x→r+1,y−>r+1x \to r+1,y->r+1 优于 max⁡(x→L,x→R),max⁡(y→L,y→R)\max(x \to L,x \to R),\max(y \to L,y \to R)。
不会写捏，跑路了。
E. qoj9677
神秘厕所题，畏惧了/kk，甚至题目没看懂……
第二天过来鞭尸：组题人说这道题昨天讲错了要补充，这下真的抽象了。

Day 2

今天有六道题！
A. CF1385E
什么神秘定向题目……直接一个拓扑序，然后拓扑序小的向大的连。
但是唐氏yq在这种地方调了将近三个小时……最开始想的dfs，然后就没有然后，硬怼dfs两小时没有结果。
B. CF1626D
唐氏yq继续发力……限制第一部分选至多 2x2^x 个数，第二部分选至多 2y2^y 个数，但是取消 2x+2y≤n2^x+2^y \le n 的限制就对了，为什么呢？（挠头）（挠头）
xza来救场了！考虑虽然实际上选取的数不超过 nn 个，但是他们加完过后就超过 nn 了，比如 3+1=4,22+20=5>43+1=4,2^2+2^0=5>4。赞神伟大！
C. CF1528D
我了个dij啊……你说得对，但是yq在看了题解后才知道答案为 xx 的时候过了 xx 秒。这充分地证明了yq喜欢不思考直接开做。挠头挠了114514分钟，最后在题解的帮助下想出等待一秒后的 disdis 转移其实可以从不等待就转移的循环移位转过来，因此取一下min就好了。
另：xza看我的代码脑袋疼。
D. CF1286C2
题目读完了吗？好的，右边有一个“查看题解”，请打开，复制其中的代码并提交，你就做完了！
滚去读了tj，然后一秒被xza问住，真是题题又解解啊。
再读一遍题解，发现可以用CF1286C1（哈哈也是一秒打开题解）解决前n/2的的问题，然后统计 fi,jf_{i,j} 表示长度为 ii 的子串中字符 jj 的出现次数。
那么直接计数 gi,j=fi+1,j−fi,jg_{i,j}=f_{i+1,j}-f_{i,j}，这就表示字符 jj 在长度为 ii 和 i+1i+1 的子串中多余出现了 gi,jg_{i,j} 次，那么这就不是答案！
维护到现在为止都不知道位置的可重字符集，删掉多余的字符，最后一定会剩下来两个字符 ai,an+1−ia_{i},a_{n+1-i}。由于 an+1−ia_{n+1-i} 先前已经解决过了，另外一个就是 aia_i 了。
唐氏yq还在发力！yq使用 s.erase(ch) 删除可重集中的字符；yq认为长度相等的字符串就是一样的；yq善于使用 ∑i=1ni=n(n−1)2\sum_{i=1}^{n}i=\frac{n(n-1)}{2} 的超强结论（甚至样例都输不完）。
E. qoj5707
来看这道题要怎么做：
  1. 不考虑那个抗体的限制直接dp，不会做。
  2. 神秘转化，听不懂。
  3. 对限制建AC自动机，不会捏。
  4. 神秘转化，听不懂。
结论：这道题能改出来我的祖坟要冒青烟。
Ex. uoj659
没有+1操作是好做的，只考虑第 tt 位。那么对应位上 |0 &1 ^0 的操作会无效，|1 &0 的操作会覆盖掉区间之前的操作，所以最后只需要统计最后一个 |1 &0 操作的位置到 rr 中 ^1 操作的次数然后直接做就好了。
考虑+1操作实质上是什么。还是按位考虑。它相当于当前位进行 ^1 操作。如果当前位为 11 的话把 +1 操作传递给下一位。分别维护 00 和 2t2^t 到哪里会因为 +1 操作而在第 tt 位归零。同时考虑第 t−1t-1 位对第 tt 位的贡献，它就是 00 或 2t2^t 因为 +1 操作归零的次数（当做 ^1 处理）。
xza看到这里问我是不是真的改不出来这些题……但是听完了和改完了根本不是一个难度啊……

Day 3

观前感慨：感情我这么多天看不到犇犇是因为开了学术模式……？
A. CF1325D
一打开，诶呀，做过！太好了一举冲破之前卡在A题 ∞\infty 年的困扰。
考虑一堆数的异或运算肯定小于等于它们的和，因此 u≤vu \le v。同时考虑这一堆数二进制下的最后一位，此时加法运算等价于异或，因此 u,vu,v 二进制下的最后一位必须相同。不满足这两条限制的直接输出 −1-1。
考虑什么时候答案为 00 或 11。如果 u=vu=v，输出一个 uu 就可以了。但是在 u=v=0u=v=0 时，什么也不输出，答案就是 00。
我们相信输出来的数不会太多，直接开莽！记 Δ=v−u2\Delta=\frac{v-u}{2}。这肯定是一个整数（参考答案为 −1-1 的情况）。构造 Δ,Δ,u\Delta, \Delta, u，这个序列满足要求。但是观察样例，还有答案为 22 的情况！原来 Δ,u⊕Δ\Delta,u \oplus \Delta 也有可能是一个解，判断是否可行即可。
B. qoj7622
不会，内卷哥过了，直接要解法。内卷哥不给，就自给自足（指找到最短代码解直接开抄）。
思考如何更好地利用这些折扣。我们可以把折扣算到它管的范围内 aia_i 最小的那个地方。然后排一下序，直接前缀和就好了。考虑这样为什么是对的。如果这个做法假了，那就意味着我们找到了一个（或多个）新的数，可以把目前解法中的这么多个数给换出去。考虑最小的数 aia_i 被换成了 aj,j<ia_j,j <i，这就意味这那些折扣全部给了 aja_j，而这样的 aja_j 一定会在排序时排在 aia_i 前面。也就是说我们会取到 aja_j 而不是 aia_i，得证。
啊啊啊要退役了，这么脑残的题都做不出来。
C. qoj9734
神秘交互题，除了让xza大神大显身手以外（毫无）用处。
xza成功用 99 次询问解决了 n=109n=10^9 的问题，这是什么？我是农夫，这是添柴！
改不动一点qwq，大概是二分其中一个端点的范围，然后找到端点后，再用两次询问确定另一个端点。
D. CF1656H
8.14改过了……死因：输出保留元素的序号而不是元素。
看起来 n,mn,m 很小，启发我们用 O(nmlog⁡(nm))O(nm\log (nm)) 的做法。考虑一个数是导致自己在的这一侧和另一侧的 lcmlcm 不一致的罪魁祸首，它就应该被删掉。参考tj大力退式子，用线段树维护这个过程，就做完了。
E. P9334
可以分大小段，然后发现小段只有一个数肯定是最优的。后边没听懂。
组题人讲的时候说贪心跳下一个小段是错的，推了半天又说贪心是对的，又说不是这个贪心，来来回回搞了一会，听不懂，润了。
内卷哥在这个时候内卷生成函数P4841，畏惧了。
Ex. qoj9438
润回来了没有听到。

Day 4

给这一天打8.6分，因为我有1.4了。
A. CF1304C
签到题。区间。过。
B. CF768E
神秘博弈题。唐氏yq开始发力：
  1. 可能为 YES 的 nn 不太多，直接套取数据（假）。被出题人随便构造一堆 YES 就浪费评测资源了。
  2. sgi{sg}_i 是斐波那契数列/是循环数列（假），yq什么也没有搞出来，还
Wrong answer on test 21
  1. sgi=[i是三角形数]{sg_i}=[i是三角形数]（假），样例都过不去yq你就寻思吧。
最后直接点击查看其他选手代码c了一个结论过来。
C. CF1821F
本来想要独立思考，一看紫题，一看2600，一看组合数学，直接放弃。
首先推了几个dp式子，发现结果都应该是偶数，那那个311是怎么回事呢？颓废一会后发现可能会有一些树在同一位置但是倒的方向不一样，所以就重复计算了。
推不出来式子，直接查看代码。诶怎么是容斥？怎么是 k+1k+1 和 2k+12k+1？这对吗？开始考虑组合意义。
容斥有 ii 颗树可以往两边倒，占用 2k+12k+1 的空间；有 m−im-i 颗树可以往一边倒，占用 k+1k+1 的空间。那么从原本的长度 nn 中减掉这些长度，就是把 n−i(2k+1)−(m−i)(k+1)n-i(2k+1)-(m-i)(k+1) 个苹果分配给 mm 个盒子（可以为空），直接启动插空插出来 (n−i(2k+1)−(m−i)(k+1)+mm){n-i(2k+1)-(m-i)(k+1)+m \choose m}，然后乘上选的哪 ii 颗树 (mi){m \choose i}，乘上容斥系数 (−1)i(-1)^i，乘上往一边倒的树可以占左倒右，占右倒左 2m−i2^{m-i}，求和即可。
赛时没想通 2m−i2^{m-i} 而是唐成 2i2^i 调了0.5h，谨记。
D. qoj6406
优秀的分类讨论。等会再补。
死因：比较运算大于打成小于号。
观察到 n+mn+m 比较小。分别考虑 n≤26n \le 26 和 n>26n>26 的情况。
如果 n≤26n \le 26，考虑状压dp，dpidp_i 表示如果到达二进制为 11 的所有点，最少需要的 aa。那么就是 max(0,dpj−bi)+ai→dpj⊕2imax(0,dp_j-b_i)+a_i \to dp_{j\oplus 2^i}，其中 jj 的二进制第 ii 位是 00。
如果 n≥27n\ge 27，那么 m−n≤18m-n \le 18,非常小。不如枚举每一个节点从哪一个点转移过来，这样形成一个树。容易发现这样枚举的复杂度是 O(∏ini)O(\prod {{in}_i})，看上去就非常对。实际上它的复杂度大概是 2m−n2^{m-n} 这个量级，所以不会超时（易得）。
如果给定的是一颗树是好做的，从下往上dfs，显然可以把两个节点 (ai,bi),(aj,bj)(a_i,b_i),(a_j,b_j) 合并成一个节点 (max⁡(ai,ai−bi+aj),bi−ai+bj−aj)(\max({a_i,a_i-b_i+a_j}),b_i-a_i+b_j-a_j)。
然后考虑合并顺序。显然是 ai≤bia_i \le b_i 的更靠前，因此分两类讨论。如果 ai≤bia_i \le b_i，就按照 aia_i 从小到大排序（都是正收益肯定前置要求越少越好）；如果 ai>bia_i>b_i，就按照 bib_i 从大到小排序（都是负收益就希望加回来的越多越好，另外补一个为什么不按照 bi−aib_i-a_i 从大到小排序是因为有反例 (7,5)(4,3)(7,5)(4,3) 会导致不优）。
一个节点一定会把比他优的儿子节点全部合并了，然后剩下的就留给父亲处理。最后再把待在根节点的所有节点全部合并，就做完了。
对于每一种 dfsdfs 出来的树跑一遍计算，取最小值，第二种情况就搞定了。
E. uoj425
折半搜索，分成前 1515 位和后 1515 位考虑，把后 1515 位得到的合法模式串扔进 bitset 里面，把前 1515 位得到的合法模式串和 bitset 里面的进行匹配，然后就得到了 O(2nqw)O(\frac{2^nq}{w}) 的超级复杂度。
组题人讲了把 qq 分块的超级优化做法，但是似乎不用也能过（？）。
Ex. uoj841
这道题是Day 1 原，但是显然yq没有改出来。而且今天也没有改。

Day 5

昨天下午四点开方舟合约，前天中午十一点开崩铁3.5，重生之我在rdfz打游戏。
更新：打专栏时xza过来搞事，之前写好的东西没了，xza你还要脸吗？
中午打杭电。偶遇1005计算几何强如怪物，拼尽全力无法战胜。被新初二生单调队列了/kk。
A. CF926G
签到题。考虑奇数。
B. uoj143
这题在魔怔。 ——组题人
xza神力！众人毫无头绪的时候率先想出正解，领先rdfz爷114514年！！！
分 aia_i 奇偶性考虑，奇数分一组，偶数分一组，然后全部除以二递归处理。容易发现等差数列不会跨奇数组和偶数组（因为跨组要求公差是奇数，同一组要求公差是偶数）。这样实质上是按照 aia_i 的二进制颠倒排序，就做完了（莫名想起来了 fftfft 的蝴蝶变换，但是一点用都没有）。
C. CF1635F
不会，直接ctj。容易发现答案点对只有 O(n)O(n) 个，直接存储。和一个点 ii 组成答案点对的点 jj 只可能是右边最左侧的或者左边最右侧的 wj≤wiw_j \le w_i。把查询离线下来，树状数组直接维护。
赛时不会求后缀和的树状数组，被 ∞\infty 个人骂不是人。改用线段树，没有 pushup（sy指出来了谢谢他），但是改了还是假了。最后ctj明白原来树状数组是这样求后缀和的。
yq已经第 ℵ1\aleph_1 次不是人了，再接再厉。
D. P8275
放弃了。xza赛时说是笛卡尔树，下午组题人讲题，居然说中了！（一部分）
E. qoj5357
没听捏。
F. qoj4898
也没听，这几天后几题直接跳了，今天直接就是没听。

Day 6

省流：打完前两题就跑路了。
A. AT_agc020_c
不像是人类。
考虑和是对称的，如果 xx 在集合里，那么 s−xs-x 也在集合里。唯一的例外是 ss。不过可以把 00 加进集合里，考虑新的中位数是从 ceil(s/2)ceil(s/2) 开始最小能被组合出来的数，bitset维护一下就做完了。
B. AT_agc023_b
先来一个 O(n4)O(n^4) 信仰暴力，显然TLE了。但是n方都可以过百万了n^4为什么不能过300
考虑优化。容易发现题目的限制是在要求 ai,j=aj+(B−A),i−(B−A)a_{i,j}=a_{{j+(B-A)},{i-(B-A)}}（都在  mod n\bmod n 下考虑），直接枚举 B−AB-A 的差值 C∈(−n,n)C \in (-n,n)，然后就是 O(n3)O(n^3)，就过了。
C. CF1175G
D. P10181
E. CF2018E2

Day 7

这两天在打CCBC，报名的人是yq，但是xza做出来了 100%100\% 的题目，你有什么头绪吗，yq？
A. AT_agc005_c
xza，古希腊掌管分讨的神，轻松AC此题。而某个抓耳挠腮的吃了∞\infty发罚时的人就不一定了，对吧，遂ctj，直接过。
思考 max⁡ai\max a_i 对最后这个树的限制。这实际上确定了树的直径。因此把直径这条链取出来，剩下的点挂在直径上是一定不劣的。加上亿点点分类讨论，就可以AC此题。
B. qoj8192
数据较水，放人一命。
m=1m=1 的情况非常简单，直接跳过。在 m=2m=2 时，二分答案 kk，然后直接贪心选取符合条件的区间（虽然并不正确）。但这样会T飞，怎么办呢？我们发现选取区间一定是从选取的区间左上角开始取的，那就只有该点是这个方向上第一个能走的点时开始尝试取区间。
最后发现怎么就只有一个点 WA了，没事改了一下枚举方向的顺序就过了。
yq在调试中取得了 −1145141919810-114514^{1919810} 的好成绩，下次还来。
C. qoj5116
赛时没过，赛后直接ctj。
维护每一个点在 2j2^j 步后可以到达的每一场比赛中最靠前的位置。查询的时候直接倍增即可。
预处理的转移非常显然，但是初值难以确定。我们需要额外维护一个数组用于处理：第 ii 场比赛中后 jj 个人在一步过后可以到达每一场比赛中最靠前的位置 gi,jg_{i,j}，这样初值就是 dpi,0=∑j=1mgj,pj,idp_{i,0}=\sum_{j=1}^{m} g_{j,p_{j,i}}，其中 pj,ip_{j,i} 为 ii 在第 jj 场比赛的位置，求和即为将这些位置信息合并。
D. P5841
E. AT_wtf22_day1_d

Day 8

虽然是Day 8但是是8.19来补的，好好思考了一下为什么8.19打的标题是8.18……没救了……
A. AT_agc019_b
签到题。翻转区间和交换首尾字母是等价的，因为如果首尾字母相同，这个区间可以由去掉首尾字母后的区间贡献，然后就做完了。
B. CF1628C
神奇构造题，写了一篇题解，不讲做法了。
我AC此题后，xza构造出来n=3的hack数据，指出题目假了。仔细重新阅读题面，发现原来 nn 是偶数。我们两个唐完了。
逛题解区，发现有人宣称自己奇数偶数所有情况都解决了，遂指出，打字的时候有一位rdfz爷路过直接带我又看了一遍 nn 是偶数，没谁了。
C. CF452F
不会，但是我们有神奇做法：发现作为答案的 ai,aj,aka_i,a_j,a_k 中 min⁡(∣i−j∣,∣j−k∣,∣i−k∣)\min(|i-j|,|j-k|,|i-k|) 不会太大（说人话就是等差数列的数之间较小的间隔不太大），于是直接暴力，然后就过了？！！
tlqtj神力！
在AC这道题过后，时间竟然是8:37，最光速的一集。
D. P5115
不会，我还有救吗……xza胡了一个SA做法，但是不会实现，巧了，我也不会。
E. qoj7415
E题一向是直接跳过的。

Day 9

今天一整天都在讲张量和矩阵乘法。啊啊啊啊啊啊……不行了我吃的shit也要让观众吃一吃。
就是考虑卷积的过程，实际上是若干形如 αiβjγk\alpha_i \beta_j \gamma_k 的线性组合，其中 RαiβjγkR\alpha_i \beta_j \gamma_k 表示 aibja_ib_j 对 ckc_k 有RR 的贡献（即 ckc_k 的组成部分中含有 RaibjRa_ib_j 项）。为了把这个东西抽象起来，我们使用矩阵的拓展版本——张量。张量是一整个线性空间，维度是线性空间的维度，当维度为 22 时可以退化成矩阵，维度为 11 时退化成数组。刚才那个东西就可以用一个 n×m×pn \times m \times p 的三维张量概括起来（n,m,pn,m,p 分别是数组 a,b,ca,b,c 的大小，下文统一认为 n=m=p=2kn=m=p=2^k）。
那么就有一个神奇的东西。我们知道卷积中乘法开销最大，所以我们规定乘法有 11 的代价，加法减法、乘一个常数都是没有代价的。具体地，定义一个“乘法节点”接受两个输入，一个是 aa 的线性组合，一个是 bb 的线性组合；节点的输出会按照权重把计算结果贡献到对应的 cc 中。举例来说，(a0+a1)×(b0−b1)→(c0−c1)(a_0+a_1) \times (b_0-b_1) \to (c_0-c_1)，就表示计算 (a0+a1)×(b0−b1)(a_0+a_1) \times (b_0-b_1) 的结果 ss，并使得 c0←c0+s,c1←c1+sc_0 \leftarrow c_0+s,c_1 \leftarrow c_1+s。其实这就是一个 33 维（每一个维度两个数）张量 α0β0γ0−α0β0γ1−α0β1γ0+α0β1γ1+α1β0γ0−α1β0γ1−α1β1γ0+α0β1γ1\alpha_0\beta_0\gamma_0-\alpha_0\beta_0\gamma_1-\alpha_0\beta_1\gamma_0+\alpha_0\beta_1\gamma_1+\alpha_1\beta_0\gamma_0-\alpha_1\beta_0\gamma_1-\alpha_1\beta_1\gamma_0+\alpha_0\beta_1\gamma_1。
我们发现我们实际上在选择一堆张量加起来并让求和的结果恰好等于 ∑i=0n−1∑j=0n−1αiβjγf(i,j)\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}\alpha_i\beta_j\gamma_{f(i,j)}，其中 f(i,j)f(i,j) 可以是自定义的位运算。但是选择的张量有什么限制呢？如果给出的系数 wa,wb,wcw_a,w_b,w_c，那么张量中必须有且仅有所有的 wa,iwb,jwc,f(i,j)αiβjγf(i,j)w_{a,i}w_{b,j}w_{c,f(i,j)}\alpha_i\beta_j\gamma_{f(i,j)}，这个限制在术语中成为张量的秩（rank）为 11。也就是说，如果一个 ll 维张量 VV 可以被表示为若干个向量 wiw_i，使得 Va1a2a3⋯al=∏i=1lwi,aiV_{a_1 a_2 a_3 \cdots a_{l}}=\prod_{i=1}^{l}w_{i,a_i}，那么这个张量的秩为 11。
这样限制就很清晰了，我们实际上是在求目标张量最少能用多少个秩为 11 的张量加起来。这被称为张量的秩，记作 rank⁡(V)\operatorname{rank}(V)。特别的，零张量（所有元素都是 00）的秩是 00。秩为 11 的张量有另外一种写法 (w1)∘(w2)⋯∘(wl)(w_1)\circ(w_2) \cdots \circ (w_l)，比如刚才举到的 α0β0γ0−α0β0γ1−α0β1γ0+α0β1γ1+α1β0γ0−α1β0γ1−α1β1γ0+α0β1γ1\alpha_0\beta_0\gamma_0-\alpha_0\beta_0\gamma_1-\alpha_0\beta_1\gamma_0+\alpha_0\beta_1\gamma_1+\alpha_1\beta_0\gamma_0-\alpha_1\beta_0\gamma_1-\alpha_1\beta_1\gamma_0+\alpha_0\beta_1\gamma_1 这么长一坨，就可以简写成 (1 1)∘(1 −1)∘(1 −1)(1 \space 1)\circ (1 \space -1)\circ(1 \space -1)。
我们先考虑 n=2n=2 的情况，这时候有只用两次乘法的方案（以或卷积为例）：c0=a0b0,c1=(a0+a1)(b0+b1)−a0b0c_0=a_0b_0,c_1=(a_0+a_1)(b_0+b_1)-a_0b_0，那么写成张量形式就是 (1 0)∘(1 0)∘(1 0)+(1 1)∘(1 1)∘(1 −1)(1 \space 0)\circ(1\space 0)\circ(1\space 0)+(1\space 1)\circ(1\space 1)\circ(1\space -1)，其中的加法就是张量对应位置相加。为了后面方便，记 (1 0)∘(1 0)∘(1 0)=T0,(1 1)∘(1 1)∘(1 −1)=T1(1 \space 0)\circ(1\space 0)\circ(1\space 0)=T_0, (1\space 1)\circ(1\space 1)\circ(1\space -1)=T_1，那么原式就可以重新写成 T0+T1T_0+T_1，这样更加简洁直观（也不用打那么多字）。
进一步考虑 n=4n=4 的情况。能否只用四次乘法就搞定呢？可以的，考虑让 α,β,γ\alpha,\beta,\gamma 形式化一点，不需要具有实际意义，而两个张量元素相乘的结果 αi0βj0γk0×αi1βj1γk1\alpha_{i0}\beta_{j0}\gamma_{k0} \times \alpha_{i1}\beta_{j1}\gamma_{k1} 等于 αi0∗2+i1βj0∗2+j1γk0∗2+j2\alpha_{i0*2+i1}\beta_{j0*2+j1}\gamma_{k0*2+j2}，这个相乘的结果可以对应一个实际意义。那么我们请出 (α0β0γ0+α0β1γ1+α1β0γ1+α1β1γ1)(α0β0γ0+α0β1γ1+α1β0γ1+α1β1γ1)(\alpha_{0}\beta_{0}\gamma_{0}+\alpha_{0}\beta_{1}\gamma_{1}+\alpha_{1}\beta_{0}\gamma_{1}+\alpha_{1}\beta_{1}\gamma_{1})(\alpha_{0}\beta_{0}\gamma_{0}+\alpha_{0}\beta_{1}\gamma_{1}+\alpha_{1}\beta_{0}\gamma_{1}+\alpha_{1}\beta_{1}\gamma_{1})，它正正好好对应 n=4n=4 时所要求的张量。诶，这不就是原本张量的平方 (T0+T1)2(T_0+T_1)^2 吗？
是的，这被称作张量的直积，可以用 A⊗BA \otimes B 表示。我们尝试给出直积更一般化的定义。先来考虑三维张量的情况。一个 n×m×pn \times m \times p 的张量 AA 和一个 n′×m′×p′n' \times m' \times p' 的张量 BB 的直积应该是一个 nn′×mm′×pp′nn' \times mm' \times pp' 的张量 CC，且 Cin′+i′,jm′+j′,kp′+k′=Ai,j,kBi′,j′,k′C_{in'+i',jm'+j',kp'+k'}=A_{i,j,k}B_{i',j',k'}，即两个张量的直积的在某一维的下标可以被看做一个两位数，而且底数是张量在那一维的长度。那么结果的下标就可以在每一位拆开成十位数和个位数，分别定位得到的两个元素相乘得到答案。这个定义可以推广到任意维度，不再赘述。注意要和矩阵乘法区分。直积和乘法一样具有分配率和结合律，和普通的乘法不一样的是它没有交换律。
那么一个数和它自己的直积就可以用 A⊗2A^{\otimes 2} 表示。把上文的符号更正一下，n=4n=4 的情况下目标张量就是 n=2n=2 时的目标张量和它自己的直积，记作 (T0+T1)⊗2(T_0+T_1)^{\otimes 2}。推广一下，n=2kn=2^k 时的目标张量就应该是 (T0+T1)⊗k(T_0+T_1)^{\otimes k}。
张量的秩有一个优美的性质：如果 A⊗B=CA \otimes B=C，那么 rank⁡(C)≤rank⁡(A)×rank⁡(B)\operatorname{rank}(C) \le \operatorname{rank}(A) \times \operatorname{rank}(B)，证明很简单，把 A,BA,B 分别拆开成秩为 11 的张量加起来，应用直积的分配率，那么就可以拆开成两个张量秩的乘积那么多个秩为 11 的张量两两相乘。而两个秩为 11 的张量乘起来秩还是 11（把它们对应的 ww 对应位乘起来再还原回张量，这样看就十分显然）。所以这个性质是成立的。
这样一来，我们成功地说明了 rank⁡((T0+T1)⊗k)≤rank⁡((T0+T1))k=2k=n\operatorname{rank}((T_0+T_1)^{\otimes k}) \le \operatorname{rank}((T_0+T_1))^k=2^k=n，也就是只需要 nn 次乘法就可以得到卷积。
我们知道乘法的次数很小了，但是还有一个问题：怎么做这些乘法？因为如果逐个乘法节点考虑 a,b,ca,b,c 的话需要 O(n2)O(n^2) 的时间复杂度，那就不可接受。所以我们需要更好的方法。
我们有如下定理：(A×B)⊗(C×D)=(A⊗C)×(B⊗D)(A \times B) \otimes (C \times D)=(A \otimes C) \times (B \otimes D)。证明的话考虑每个位置上两个式子分别在干什么就不难了（其实是我没听懂qwq）。那么令 M=T0+T1M=T_0+T_1，计算 M⊗kM^{\otimes k} 有一个做法：M⊗k=∏i=1k((⊗j=1j<iI)⊗M⊗⊗j=i+1j≤kI)M^{\otimes k}=\prod_{i=1}^{k}((\otimes_{j=1}^{j<i}I)\otimes M \otimes \otimes_{j=i+1}^{j \le k}I)，举一个 k=3k=3 的例子就是计算 (M⊗I⊗I)×(I⊗M⊗I)×(I⊗I⊗M)(M \otimes I \otimes I)\times(I \otimes M \otimes I)\times(I\otimes I \otimes M)。考虑每一项的含义是只考虑这一位时的卷积结果，所以这可以解释为什么按位拆开考虑卷积是对的。
另外提一嘴，这只是 FWTFWT，如果要求 IFWTIFWT 的话需要把 MM 换成 M−1M^{-1}。比如或卷积里的 MM 可以写成一个矩阵（计算表）[1011]\begin{bmatrix}1 & 0 \\1 & 1\end{bmatrix}，那么 M−1M^{-1} 就长这样 [10−11]\begin{bmatrix}1 & 0 \\-1 & 1\end{bmatrix}
我们来做一个《非常简单》的练习题。刚才搞定了或卷积的 MM，现在可以搞定异或卷积的 MM。还是考虑 n=2n=2 的情况，此时 c0=a0b0+a1b1,c1=a1b0+a0b1c_0=a_0b_0+a_1b_1,c_1=a_1b_0+a_0b_1，那么记录 h0=(a0+a1)(b0+b1),h1=(a0−a1)(b0−b1)h_0=(a_0+a_1)(b_0+b_1),h_1=(a_0-a_1)(b_0-b_1)，我们恰好发现 c0=h0+h12,c1=h0−h12c_0=\frac{h_0+h_1}{2},c_1=\frac{h_0-h_1}{2}，写成张量形式就是 ()(1 1)(1 1)(1/2 1/2)(1 −1)(1 −1)(1/2 −1/2)(\frac{}{})(1\space 1)(1\space 1)(1/2 \space 1/2) (1 \space -1)(1 \space -1)(1/2 \space -1/2)
还有一段，没时间就不补了/kk。

Day 10

最后一天了，说些什么呢……
我勒个全at啊，内卷哥狂喜
怎么只有四道题……有四道题也好其实……
A. AT_agc036_a
神秘签到题，直接考虑向量叉积，然后构造出来 s=⌈S⌉s=\lceil \sqrt{S} \rceil，看到这个东西后面就没什么障碍了。
B. AT_agc037_b
古希腊掌管分类讨论的神，救救我啊……
首先有一个贪心解，每个字母从左往右数依次分给 nn 个人。容易发现只有相同地位（每个人拿到的第几个字母）的字母会发生交换，分类讨论字母的地位是 p1,p2,p3p1,p2,p3 即可。
C. AT_agc001_e
直接ctj。
考虑范德蒙德恒等式，原式（变形后）可以展开成 ∑f(k)f(−k)\sum f(k)f(-k)，其中 f(k)=∑(ai+biai+k)f(k)=\sum {a_i+b_i \choose a_i+k}，然后复杂度的瓶颈在 f(k)f(k) 的计算上。直接启动生成函数 ∑(ai+biai+k)xk\sum {a_i+b_i \choose a_i+k}x^k，经过变换过后搞成 ∑∑ai+bi=kx−ai(1+x)k\sum \sum_{a_i+b_i=k} x^{-a_i}(1+x)^k 大概这样子就好了。
D. AT_agc001_f
不会捏。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...