tuwenshuo的学习笔记

· · 个人记录

本文将会将知识分成8个块，记录作者学习的算法和刷过的值得纪念的题 :::info[目录]

学习区
--语法
--算法
--DP
--数据结构
--图论
--数学
----数论
------因数，倍数
------质数，合数
------质因数分解，唯一分解定理
------原根
------BSGS
----几何
----抽象数学
--串串
刷题区
--云剪贴板5o23o6nz（配tag：概念题，博弈论）
--P1429（配tag：人类智慧，排序，数学）
--P6247（配tag：人类智慧，排序，数学）
--P7883（配tag：人类智慧，排序，数学）
--P10102（配tag：矩阵，随机化，人类智慧）

::: ::::::info[学习区] :::info[语法] 有时间了再出 ::: :::info[算法] ::: :::info[DP] ::: :::info[数据结构] ::: :::info[图论] ::: :::::info[数学] ::::info[数论] 此处仅针对正整数域 :::info[因数，倍数] 当a除以b没有余数，那么a是b的倍数，b是a的因数，记作 b\mid a，反之记作b\nmid a ::: :::info[质数，合数] 定义：只有1和它本身2个因数的数叫质数，否则叫合数，注意了，1不是质数。
即\forall1\lt i\lt n ,i\nmid n代表n是质数,\exist1\lt i\lt n ,i\mid n代表n是合数 ::: :::info[质因数分解，唯一分解定理] 质因数分解定义：将任何一个大于等于2的数表示为一个或多个质数相乘，形式化的，定义p_i为质数，则将x质因数分解结果是\overset{m}{\underset{i=1}{\Pi}}p_i^{t_i}，如504=2^3\times 3^2 \times 7
质因数分解性质：在考虑乘法交换律的情况下只有一种，这就是唯一分解定理 ::: ...(中间先不写) :::info[原根] 由欧拉定理可知，\forall\gcd(a,m)=1,a^\varphi(m)=1(\mod m)且若x是满足a^x=1(\mod m)的最小正整数（x叫做a在\mod m意义下的阶）,则有x\mid\varphi(m)。
当一个数x满足x在\mod m意义下的阶是\varphi(m)，则x是\mod m的原根，当且仅当m等于2或4或是奇素数的次方或是奇素数的次方的二倍时m才有原根且一定有\varphi(\varphi(m))个。
给出一个\mod m的原根x，\forall \gcd(i,\varphi(m)),x^i是\mod m的原根。
根据以上内容，你一定学会了已知最小原根如何求所有原根，那么如何求最小原根呢？暴力即可。但也不能太暴力了，给你一个东西来判断原根吧。

bool is_primitive_root(int g, int n, const vector<int>& phi_prime_factors) {//AI生成代码，给定g,n,n的所有因数，如果g是n的原根，则返回1，否则返回0
    if(__gcd(g, n) != 1) return false;
    if(mod_pow(g, phi[n], n) != 1) return false;
    for(int q : phi_prime_factors) {
        if(mod_pow(g, phi[n] / q, n) == 1) {
            return false;
        }
    }
    return true;
}
好的，你学会了如何判断原根了，来做一下这道题吧。
依据你之前发明模意义下乘法逆元的过程，来发明一下模意义下对数表吧。 ::: :::info[BSGS] 别看它被戏称“北上广深”，它非常简单，只需要lxl最喜欢的分块就行。我们讲这道模板题
我们先选择一个数k，然后设集合S=\{nb^i\mod p\mid 1\leq i\leq k\}的结果，然后\forall x\le p/k+10(此处10可以改为其它数字，目的是使p-1及以内的数字都不漏)观察是否满足b^{kx}\mod p\in S，如果是的，观察在i等于几时nb^i\equiv b^{kx}(\mod p)并结束枚举，答案为kx-i，是不是有点像lxl最喜欢的分块？没错它就是，易得k=O(\sqrt{p})能使得时间复杂度最小，为O(\sqrt{p})，好的做模板题吧。 ::: :::: ::::info[几何] :::: ::::info[博弈论] :::info[概念表]		 专有名词 通俗表示
合作/非合作博弈 就看需不需要合作，因为评测机没装AI非合作博弈研究的好，所以都出非合作博弈的题
对称/非对称博弈 动作收益是否依赖角色
零和/非零和博弈 就看总收益，一定是0就是零和，否则非零和
同时/序贯博弈 回合制/非回合制
完美/不完美信息博弈 对方是/否明牌
完全/不完全信息博弈 目的与好坏（包括量）是否知道
组合博弈 暴力无法出奇迹，不可循环，组合博弈出题主要出：序贯完美信息完全信息不随机博弈
公平/非公平组合博弈 动作不依赖/依赖身份
正常/反常博弈 针对组合博弈，最后一步赢是正常博弈，最后一步输的是反常博弈，当然有的博弈既不正常也不反常

去下面的 云剪贴板5o23o6nz 看例题吧。 ::: :::info[] :::: ::::: :::info[串串] ::: :::::: ::::info[刷题区] :::info[云剪贴板5o23o6nz] T1:ACEHIQ
解析：
A,B:可以和他约定谁选2谁以后对方都选2，就组成了联盟，就是合作博弈
C,D:收益表将字“你”和“邻居”换过来都是一样的，是对称
E,F:显然这不是自己干自己的吗，同时。
G,H:分开的，看不到，不完美信息。
I,J:表不是给你了吗，完全信息。
K,L,M,N,O:这个游戏就4种选择，就不是组合，那剩下的不就都不是了吗。
P,Q:易得自己和邻居都按1可以总收益2000，其它同理不零和。

T2:BDEHIQ
解析：
A,B:这次交流不了了，非合作。 其他的T1举一反三一下就行了

后面略。 ::: :::info[P1429] 正解较难，考虑人类智慧。
我们充分发扬人类智慧：
将所有点分别按x\div y,x^2+y^2,x,y,x\times y排序。
根据数学直觉，在排序后，最近的两个点在数组中肯定不会离得太远，最远的两个点在数组中肯定不会离得太近。
所以只取每个点向后的50个点更新最近距离，并取最后向前的50个点更新最远距离。 这样速度快到飞起，用前两个即可在时限内卡过。 ::: :::info[P6247] 正解较难，考虑人类智慧。
我们充分发扬人类智慧：
将所有点分别按x\div y,x^2+y^2,x,y,x\times y排序。
根据数学直觉，在排序后，最近的两个点在数组中肯定不会离得太远，最远的两个点在数组中肯定不会离得太近。
所以只取每个点向后的50个点更新最近距离，并取最后向前的50个点更新最远距离。 这样速度快到飞起，全用可以在时限内卡过。 ::: :::info[P7883] 正解较难，考虑人类智慧。
我们充分发扬人类智慧：
将所有点分别按x\div y,x^2+y^2,x,y,x\times y排序。
根据数学直觉，在排序后，最近的两个点在数组中肯定不会离得太远，最远的两个点在数组中肯定不会离得太近。
所以只取每个点向后的50个点更新最近距离，并取最后向前的50个点更新最远距离。 这样速度快到飞起，用前两个即可在时限内卡过。 ::: :::info[P10102] 可恶人类智慧题。
在前面乘上一个随机1\times n矩阵就行了 ::: ::::