wxyww

分类

未归档(12) 精品(28) 题解(65)

/ 注册

全部文章（共395篇）

博弈论

SG函数作用对于一个状态i为先手必胜态当且仅当SG(i)!=0。转移那怎么得到SG函数尼。 SG(i)=mex(SG(j))（状态i可以通过一步转移到j）首先说一下mex。一个集合的mex是最小的没有出现在这个集合里的非负整数。其实想一下这个也是挺明显的。状态i是先手必败态当前仅当i转移...

2020-05-22

1 502

用杜教筛求解数论函数前缀和

杜教筛用来求数论函数前缀和。复杂度为前提如果我们要求，那么需要找到一个数论函数，满足的前缀和可以非常快速的求出来，并且的前缀和可以非常快速的求出来。推导既然的前缀和可以非常快速的求出来，我们就求的前缀和。即。然后我们想得到的是。所以我们让上面的式子减去一个。对于后面这个式子,我们用来代...

2020-05-22

1 570

快速沃尔什变换小记

概述是用来处理集合卷积的问题。也就是求解类型的问题。其中或运算可以改为。寻找点值因为总是看不下去那么长的推导，所以每次都是看到一半。然后就在加上自己的一点理解，简单推导一下吧（背过结论就行）以或运算为例。为什么说是集合卷积呢。因为或运算等价于求集合并。也就是求。那么我们类似于，先将他转化...

2020-05-22

1 563

数学知识点整理

这篇文章主要是整理一些定理，方便后面复习。没有证明(学OI要什么证明)。数论相关常见的积性函数单位函数欧拉函数表示小于等于n的数字中与n互质的数字个数。莫比乌斯函数正因子数因子函数易知一般记作常值函数幂函数特别的，常记作狄利克雷卷积对于两个数论函数，其中*为狄利克雷卷积...

数学

2020-05-22

1 631

【每日一题】小AA的数列

solution 先对求一遍前缀异或和。首先肯定要按二进制位处理，假设处理到了第x位，然后枚举一个位置，我们就想要查询所有满足且为偶数的中满足，其中表示第i个位置的第个二进制位上的值。所以我们只要根据奇偶性分一下类，然后做前缀和就可以求出所有满足条件的的个数了。 code /* * @Autho...

二进制

2020-05-22

1 716

【每日一题】中位数图

solution 处理出一个数组t，如果那么，否则。然后我们只要找到一个包含b所在位置的区间满足就可说明这个区间内的中位数为。所以对求一遍前缀和，记录下所在位置左边的所有前缀和值的数量。然后枚举所在位置的右边，统计答案即可。 code /* * @Author: wxyww * @Date: ...

思考题

2020-05-21

1 606

【每日一题】图的遍历

solution 我们从1号点开始染色，标记为0的点表示可以从1号点走偶数步到达，标记为1的点表示可以从1号点走奇数步到达。最后就是想要所有点都可以标记为0。如果存在一个奇环，那么这个环上的点既可以标记为1，也可以标记为0，所以所有与这个奇环相连的点都可以标记为0和1。所以我们只要保证最终连接成一...

搜索

2020-05-20

1 781

【每日一题】简单瞎搞题

solution 用表示前k个区间能(1)不能(0)组成这个数字。然后枚举一下第个区间所选的数字x，就有转移最后数一下有多少数字可以被组成就行了。但是这样复杂度爆炸，发现f的值只有和所以可以用进行优化，复杂度 code /* * @Author: wxyww * @Date: 2020-05...

背包 bitset

2020-05-19

2 0

【每日一题】比赛

solution 先考虑对于如何求出解出第道题的概率。直接求并不好求，但是解不出第道题的概率很好求，就是。那么解出第到题的概率就是。因为题目数量非常小。所以可以枚举每道题是否解出来了，然后统计一下每种情况的概率，记录到答案里面即可。 code /* * @Author: wxyww * @Date...

状态压缩概率

2020-05-18

1 662

【每日一题】NC53676「土」秘法地震

solution 因为地震的区域是固定的。所以枚举一下地震矩形的右下角，然后判断一下这个矩形内是不是含有1就行了。怎么判断一个矩形内是不是有1？二维前缀和一下，然后计算一下查询矩阵得和是不是比0大就行了。 code /* * @Author: wxyww * @Date: 2020-05-17...

2020-05-17

2 916