I . We love string 分治 容斥！！ 将所有长度相同和模式串分到一个组中，使用一个类对象来表示一个组； fSf_S fS​ 表示能于集合SSS内的所有正则表达式匹配的的字符串个数 集合SSS 用二进制数表示 考虑到所有模式串的长度之和不超过 400400400 ，所以当模式串的长度小于202020,时模式串可能会比较多，可采用暴力枚举。如果模式串长度大于 202020 那么个数不会超过 202020 个。 重复数的计算： 如果一个集合sks_ksk​中包含了第 jjj 个模式串，设在当前集合中去除 第jjj 个模式串得到集合为 sms_msm​, 由于模式串的增加，相当于是增加...

牛客多校七 C 将每一个数看成是 303030 位二进制整数 只要确定了 a1a_1a1​, 剩下的数就都确定了 ， 因为 ai+1←bi⊕aia_{i+1} \gets b_i \oplus a_i ai+1​←bi​⊕ai​ a2←b1⊕a1a_2 \gets b_1 \oplus a_1a2​←b1​⊕a1​ a3←a2⊕b2←a1⊕b1⊕b2a_3 \gets a_2 \oplus b_2 \gets a_1 \oplus b_1 \oplus b_2a3​←a2​⊕b2​←a1​⊕b1​⊕b2​ a4←a1⊕b1⊕b2⊕b3a_4 \gets a_1 \oplus b_1 \...

和高等代数有关 注意事项 集合中没有重复的元素。 要特判 000 初始在集合中的情况 结论在 z≠z∧z≠y∧x≠0∧y≠0z \ne z \land z\ne y \land x \ne 0 \land y\ne 0z​=z∧z​=y∧x​=0∧y​=0 , 的情况下 可以通过一些操作使 zzz 在集合中出现 的充要条件是 z mod gcd⁡(x,y)=0z \bmod \gcd(x,y) = 0zmodgcd(x,y)=0 证明如下： 设 d=gcd(x,y)d = gcd(x,y)d=gcd(x,y) 一定存在正整数 k1,k2k1, k2k1,k2 使得 x=k1×d...

小富的idea 题目链接 可以先计算出任意两点间的融合时间, 时间复杂度 O(n2)O(n^2)O(n2)对融合时间排序，然后从小到大枚举，如果当前时间下对应的两个点不在一个连通块中则合并连通块的个数减一；对于时间1,10001,10001,1000，可以离线预处理出来每一个时间点的个数。 实现技巧： 将两个墨点的编程和其融合时间作为一个复合类型； 计算时间时应当进行上取整； 一开始时所有时间点的连通块个数为 nnn; 更新时只需要 ti←min⁡(ti,ri−1)t_i \gets \min(t_i,r_{i-1})ti​←min(ti​,ri−1​) tit_iti​ 是 iii 时间点...

萌新联赛D 要记得开 longlonglong long longlong 不然通过率 %0\%0%0 ! 方法一 多观察 2=2202 = 2^{2^0}2=220 2⋅2=2212 \cdot2 = 2^{2^1}2⋅2=221 221⋅221=2222^{2^1} \cdot 2^{2^1} = 2^{2^2}221⋅221=222 22i⋅22i=22i+12^{2^i} \cdot 2^{2^i} = 2^{2^{i+1}}22i⋅22i=22i+1 由次可以从 222 开始每次乘以它本身 循环 n 次即可得出答案 参考代码 #include<iostream> usin...

题目关题信息： 所有区间是包络的(指一个区间被另一个区间完全覆盖)或者不交的（因此可看成树形结构进行dfs） 相关知识 交换两邻的两个数会改一个区间逆序对数量的奇偶性; 非降序的排列的逆序对儿的数量个数为 000; 思路： 将区间化成树形结构每个叶子节点包含三个值 l,r,k{l,r,k}l,r,k 左，右端点的值和当前区间的奇偶性; 在转化成树形结构时让每个区间只作为长度最小的能包络它的子区间，也就是说让每个区间最多只会被算作一次子节点 （孙子节点可以被算作多次）; 一个区间可能没有其被子区间完全覆盖，但并不影响计算因为在子区间之间的点是升序的不会产生逆序对儿； 每个区间初始时放...

C 萌新向题解二分图匹配与竞赛图综合题 题目链接 经验教训 ： 题中要求了 i,i+ni,i+ni,i+n 之间没有边也就是转化形成的图是竞赛图且没有自环； 要仔细看题 题中明确给出了是有 n⋅(n−1)÷2n\cdot(n-1) \div2n⋅(n−1)÷2 条边 相关前置知识 完全图 是指每个顶点都和其他所有点有直接边相连的图； 竞赛图就是有向完全图； nnn 阶图是指图中有 nnn 个点； 竞赛图一定是连通的，但不一定是强连通的； 若竞赛图中包含环，那么图中至少包含三个点，即不存在二元环； 哈密顿路径是指每个点都只经过一次的路径 强连通分量是极大强连通子图； 竞赛图必然存在哈密顿路...

牛客多校 jjj 题 以 dpijdp_{ij}dpij​ 表示前 iii 个数中最小后缀和为 jjj 的方案数 最小后缀和不会大于 mmm ,因为如果左边是连续的两个正数那么只会加一个，其最大值为 m 由于下标不能为负数所以将 [−m,m][-m,m][−m,m] 映射到 [0,2m][0,2m][0,2m] 如果 jjj 大于等于 000 由于每一个位置的数最大不超过 mmm,如果第 i−1i-1i−1 个数小于 j−mj-mj−m, 前 iii 个数的最小后缀和会小于 jjj 于是 dpi,j=dp_{i,j} = dpi,j​= ∑k=j−mmdpi−1,k\sum_{k = j-...