终于又做了一道线性基！ 前缀线性基求区间最大异或值 Operation Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others) Total Submission(s): 1073 Accepted Submission(s): 337 Problem Description There is an integer sequence a of length n and there are two kinds of operations: 0 l r: select some number...

题目链接 题意：给定n个整数，求满足子集异或和为0的子集大小之和。 题解：相当于求每个数出现在子集中的次数之和。 先对n个数求线性基，设线性基大小为r，可以分别计算线性基内数的贡献和线性基外数的贡献   线性基外：共n-r个数，枚举每个数x，将线性基外剩余的n-r-1个数任意排列，显然共有2n-r-1 个集合，这些集合再异或x的结果还是能被线性基异或出，所以x的贡献为2n-r-1  线性基内：枚举每个数x，将所有剩余的n-1个数再求一次线性基，设为B，分两种情况：  (1) x不能被B异或出。那么显然x不能在任意一个集合中出现，x的贡献为0。 (2) x可以被B异或出。此时B的大小必定也为r，...

最最详细的解析 基础学习 简洁明了的讲解 小小总结  总状态数不超过     2   n   −   1    2n-1   2n−1（包括初始状态）。 统计每个     e   n   d   p   o   s    endpos   endpos等价类出现位置数量时，要按长度从长到短的计算     c   n   t    cnt   cnt。那为什么一定要从长到短呢？（比如回文自动机就直接是按照节点编号从大到小计算     c   n   t    cnt   cnt）罪魁祸首就是复制得到的     n   q    nq   nq，因为它的节点编号比较大，却又要插入到节点编号比它小的...

洛谷-P3805板子题 关键点:  要有两个字符串，且处理后的字符串长度略大于原串2倍（肯定     <   2   n   +   10    <2n+10   <2n+10） p数组的更新 mid和r的转移  //#pragma comment(linker, "/STACK:102400000,102400000") #include "bits/stdc++.h" #define pb push_back #define ls l,m,now<<1 #define rs m+1,r,now<&l...

小小总结  千万记住insert完以后要build!!!老是忘掉QAQ insert函数就只是trie数的插入函数，可在结尾根据条件打一些标记 build函数(构建fail树)，主要利用BFS match函数中跑fail树其实就是反复跑后缀 fail树上倒过来建树以后可以进行很多高端操作，比如阿狸的打字机(也许还能树剖一下QAQ) match函数中跑fail树过程可以转化为打标记，而避免重复跑一个相同的后缀，常见优化(见下面的二次加强版板子题) AC自动机常与数位DP结合，毕竟数字和字符串长得差不多  洛谷-P3808 简单板子题 //#pragma comment(linker, &quot...

洛谷-P4052 文本生成器 题目地址 虽然这题应该称为记忆化搜索，但是就想当做数位DP(QAQ) 一开始数组开小了，导致了WA，TLE，RE以及两个AC，深深的体会到了数组开小了什么错误都有，哈哈 题意：给出一个字典，求长度为M且包含字典中至少一个单词的文本有多少个。 思路：   虽然是要求可读文本的数量，但是毕竟要构造多字符串的匹配还是比较麻烦的，因此可以转化为求 总文本数-不可读文本数  转化后总文本数可以直接快速幂搞定，不可读文本数可以在AC自动机上跑数位DP，别跑那些认识的单词就行啦！  题目描述 JSOI交给队员ZYX一个任务，编制一个称之为“文本生成器”的电脑软件：该软件的使用者...

洛谷 P-2292 L语言 一道比较简单的题，结果自己脑补了各种奇葩(错误)的判断，搞了一个多小时。。。 题意：用已知字典去识别一个串，求最长可识别前缀（指能将此前缀分解为字典里面的单词） 思路：  建好AC自动机，记录好每个点所代表的字符串的长度 拿要匹配的串从前往后匹配，若某个点完全不能匹配，直接退出（可以不考虑这个） 处理好什么叫“可以匹配”就好了，就是能将当前串分解为一个可识别的前缀和一个可识别的后缀即可 因此对当前字符跑fail边（即跑后缀），若“可以匹配”，则更新最长可识别前缀，并标记当前串（也是一个前缀）可识别  题目描述 标点符号的出现晚于文字的出现，所以以前的语言都是没有标点...

洛谷 P3041 视频游戏的连击Video Game Combos 难度一般，不过这个数位DP其实应该叫做记忆化搜索 题意：玩游戏时可以通过按键组合打出combo技能；然后是已知N个combo的按键方式，然后求K次按键最多可以放出的combo技能（combo技能之间可以重叠）。 思路：  在AC自动机上如果一个点表示一个字符串以及它的后缀，则一个点可以对应多个combo技能（这是关键点） 可以先用拓扑排序处理出每个点对应了多少个combo技能，处理时要用fail的反向边即refail计算入度 然后就是数位DP啦，这题没啥坑点，思路简洁  题目描述 Bessie is playing a vid...

洛谷 P-4045 密码 记AC的第一道黑题！ 题意：已知一段密码包含了一些字符串，然后求满足条件的密码有多少个，数量小于42时还得全部输出 思路：  一开始WA了两个点，不知道WA的什么，索性把读入的字符串去重了，实际上不需要 建好AC自动机，同时记录当前点是哪个字符串的结尾，方便状态压缩 做一遍数位DP，如果所有状态(给的字符串)都能达到，则说明所构造出的密码有效 需要注意的是，加入一个字符后，整条fail边上的状态都能达到了，因为fail边上的点代表是当前点的后缀字符串（这就是WA的那两个点） 最后考虑小于42时的输出，显然再跑一边相同的dfs不就行了吗？把构造出来的密码放到set里面，...

推荐博客 先记录个板子 //#pragma comment(linker, "/STACK:102400000,102400000") #include "bits/stdc++.h" #define pb push_back #define ls l,m,now<<1 #define rs m+1,r,now<<1|1 #define hhh printf("hhh\n") #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) ...

后缀自动机板子题 题意：给了一个字符串，然后里面有些子串出现次数大于1，求这种子串的出现次数乘以子串长度的最大值。 思路：  正常建好后缀自动机，将所有的np节点出现次数赋值为1 记录所有的父节点有几个儿子(不是后缀自动机上的儿子数，而是parent tree上的儿子数) 利用topo排序的思路更新所有节点的出现次数 然后就是更新答案  //#pragma comment(linker, "/STACK:102400000,102400000") #include "bits/stdc++.h" #define pb push_back #define ...

找相同字符 题意：给定两个字符串，在两个字符串中任选子串，求两子串相同的方案数 思路：  用后缀自动机处理两个字符串，一般考虑在中间插入一个用不到的字符（比如’#’），然后将它们组成一个串(后来发现好像不能插’#’，毕竟我数组第二维只开了26的大小；然后有一个方法就是把数组开成27的，然后插入一个数字26就行了) 分别记录每个节点有多少个属于第一个字符串和第二个字符串的endpos，最后累加答案即可 注意爆int，叠加答案采用      1   L   L   ∗   c   n   t   [   i   ]   [   0   ]   ∗   c   n   t   [   i   ]  ...

品酒大会 又一道黑题！以为自己     O   (   n   )    O(n)   O(n)的算法常数过大才TLE的，因此最终代码加了一堆优化（不过现在把register全给删了，不然有点难看），2333 后面发现得加差分以及后缀思想才是     O   (   n   )    O(n)   O(n)。。。不过也好，跑起来速度挺快的。 题意：有一个字符串，字符串第i个位置有权值a[i]，求出所有r相似方案数以及r相似的最大美味值，美味值定义为a[i]*a[j]，其中i，j为r相似(相似的具体定义见下方题干) 思路：  由于r相似定义为长度为r的相同子串，且有用的权值为两个字符串的首位置，...

回文自动机 小小总结：  别忘了写上初始化！ 当字符串下标从     0    0   0开始时，     p   o   s    pos   pos初始化为     −   1    -1   −1；若从     1    1   1开始，则     p   o   s    pos   pos初始化为     0    0   0；最终的     p   o   s    pos   pos代表最后一个字符的下标（前者为     n   −   1    n-1   n−1,后者为     n    n   n）。 根据本质不同的回文子串数量不超过     ∣   s   ∣    |s...