Neovim常用API
vim.bo.filetype
网络空间安全概论
导论
《中华人民共和国密码法》2019年10月29日,《数据安全法》2021年6月,《个人信息保护法》2021年8月,欧盟《通用数据保护条例》。
熊猫烧香,DarkSide,WannaCrypt勒索病毒。
无条件安全,敌手即使拥有无限的计算能力也能保障密码系统的安全性,只有一次一密是无条件安全。
计算安全敌手的计算资源是有限的条件下能保障密码系统的安全性。
破译密码的代价超过了被加密信息的价值。
破译密码所需要的时间超过了信息的保密期限。
理论安全,即使攻击者有无限的计算时间和存储空间也不能攻破 ;密码在理论上是不安全的,⼀次⼀密在理论上是安全的,穷举攻击可以找到所有可能的结果,但无法判断哪个是正确的。
实践上的安全,⼀个密码不能在合理的时间、内存、硬件、能力、金钱等条件下破解。
密码学基础
对称加密,加密和解密使用相同密钥。
C=Enk(m)C=En_k(m)C=Enk(m),m=Dek(C)m=De_k(C)m=Dek(C)。
CCC 明文,EnEnEn 加密算法,kkk 密钥,mmm 密文,DeDeDe 解密算法。
凯撒密码,平移三位;单表代换密码,任意 ...
非线性方程的数值解
二分法
求解 f(x)=0f(x)=0f(x)=0,首先取一段区间 [a,b][a,b][a,b],若 f(a)f(b)≤0f(a)f(b)\le0f(a)f(b)≤0,说明 [a,b][a,b][a,b] 区间上存在零点。通过不断地把函数零点所在的区间一分为二,使区间的两个端点逐步逼近零点,进而得到零点近似值。
假设 a0=aa_0=aa0=a,b0=bb_0=bb0=b,第 kkk 步迭代的零点区间为 [ak,bk][a_k,b_k][ak,bk],近似解为 xk=ak+bk2x_k=\frac{a_k+b_k}{2}xk=2ak+bk,精确解为 x∗∈[ak,bk]x^\ast\in[a_k,b_k]x∗∈[ak,bk]。则 ∣xk−x∗∣=∣ak+bk2−x∗∣≤bk−ak2=bk−1−ak−122=⋯=b0−a02k+1=b−a2k+1|x_k-x^\ast|=\left|\frac{a_k+b_k}{2}-x^\ast\right|\le\frac{b_k-a_k}{2}=\frac{b_{k-1}-a_{k-1}}{2^2}=\cdots=\frac{ ...
数值积分
引言
若函数在 f(x)f(x)f(x) 在区间 [a,b][a,b][a,b] 上连续,且原函数为 F(x)F(x)F(x),则有 Newton-Leibniz 公式 ∫abf(x)dx=F(b)−F(a)\int_a^b f(x)\mathrm d x=F(b)-F(a)∫abf(x)dx=F(b)−F(a)。在实际情况中,f(x)f(x)f(x) 的原函数往往过于复杂甚至难以求解,我们不得不用数值积分的方式得到定积分的近似解。
数值积分就是对于 f(x)f(x)f(x),选择合适的离散点 a≤x0<x1<⋯<xn≤ba\le x_0<x_1<\cdots<x_n\le ba≤x0<x1<⋯<xn≤b,并给离散点的函数值 f(xk)f(x_k)f(xk) 合适的权值 AkA_kAk,从而构造出近似解: ∫abf(x)dx≈∑k=0nAkf(xk)\int_a^b f(x)\mathrm dx\approx\sum\limits_{k=0}^n A_kf(x_k)∫abf(x)dx≈k=0∑nAkf(xk)。记 ...
最小二乘法拟合
曲线拟合思想
由实验或观测提供的数据往往很多,我们希望由给定的数据 (xi,yi) (i=1,2,⋯ ,n)(x_i,y_i)\ (i=1,2,\cdots,n)(xi,yi) (i=1,2,⋯,n),构造出近似函数 φ(x)\varphi(x)φ(x),不要求 φ(x)\varphi(x)φ(x) 完全通过所有的数据点,只要求所得的近似曲线能反映出数据的基本趋势。
定义拟合函数在 (xi,yi)(x_i,y_i)(xi,yi) 处的残差 εi=φ(xi)−f(xi)\varepsilon_i=\varphi(x_i)-f(x_i)εi=φ(xi)−f(xi),最小二乘法拟合曲线的要求便是 ∑i=1nεi2\sum\limits_{i=1}^{n}\varepsilon_i^2i=1∑nεi2 最小。
直线拟合
对于给定的数据点 (xi,yi) (i=1,2,⋯ ,m)(x_i,y_i)\ (i=1,2,\cdots,m)(xi,yi) (i=1,2,⋯,m),求拟合直线 y(x)=a0+a1xy(x)=a_0+a_1xy(x)=a0+a1x,使总误差最小。记 ...
生日悖论
问题描述
不考虑出生年份,一个房间中至少多少人,才能使其中两人生日相同的概率达到 $50\%$?
解
设一年有 nnn 天,房间里有 xxx 人。
设 xxx 人生日互不相同为事件 AAA,则事件 AAA 发生的概率为
P(A)=∏i=1x(n−i+1)nx=∏i=1x−1(1−in)P(A)=\frac{\prod\limits_{i=1}^x(n-i+1)}{n^x}=\prod\limits_{i=1}^{x-1}\left(1-\frac{i}{n}\right)
P(A)=nxi=1∏x(n−i+1)=i=1∏x−1(1−ni)
至少有两人生日相同的概率为 P(A‾)=1−P(A)≥12P(\overline A)=1-P(A)\ge\frac{1}{2}P(A)=1−P(A)≥21,等价于 P(A)≤12P(A)\le \frac{1}{2}P(A)≤21。
由不等式 1−x≤e−x1-x\le e^{-x}1−x≤e−x,有 ∏i=1x−1(1−in)≤∏i=1x−1ein\prod\limits_{i=1}^{x-1}\left(1-\frac{i}{n}\ ...
解码 RSA
RSA简介
明文 MMM,密文 CCC。
n>Mn>Mn>M,且 nnn 为两个不相同大质数的乘积 n=pqn=pqn=pq,1<e<φ(n)1<e<\varphi(n)1<e<φ(n) 与 φ(n)\varphi(n)φ(n) 互素,ed≡1(modφ(n))ed\equiv1\pmod{\varphi(n)}ed≡1(modφ(n))。
公钥 n,en,en,e,私钥 ddd,利用分解大质因数的困难来保证数据安全。
加密 C=Me mod nC= M^e\bmod nC=Memodn。
解密 M=Cd mod nM= C^d\bmod nM=Cdmodn。
证明解密的正确性
当 gcd(M,n)=1\gcd(M,n)=1gcd(M,n)=1,由扩展欧拉定理 Cd≡Med≡Med mod φ(n)≡M(modn)C^d\equiv M^{ed}\equiv M^{ed\ \bmod\ \varphi(n)}\equiv M\pmod nCd≡Med≡Med mod φ(n)≡M(modn)。
当 gcd(M,n)≠1\gc ...
2021牛客暑期多校4 B.Sample Game
题目大意
玩一场游戏,每一轮在 [1,n][1,n][1,n] 中随机生成一个整数 xxx,生成 xxx 的概率为 pxp_xpx。若 xxx 不小于之前生成的任何数,则游戏继续并进入下一轮,否则游戏结束。假如说最后游戏共进行了 lenlenlen 轮,则游戏的得分为 len2len^2len2。求游戏分数的期望值 E(len2)E(len^2)E(len2),答案(mod998244353)\pmod{998244353}(mod998244353) 输出。
输入为 nnn 个数 w1,w2,⋯ ,wnw_1,w_2,\cdots,w_nw1,w2,⋯,wn,pi=wi∑j=1nwjp_i=\frac{w_i}{\sum\limits_{j=1}^n w_j}pi=j=1∑nwjwi。
思路
游戏生成的数字序列一定是类似 1,1,⋯ ,1,2,2⋯ ,3,3⋯1,1,\cdots,1,2,2\cdots,3,3\cdots1,1,⋯,1,2,2⋯,3,3⋯,即 [1,n][1,n][1,n] 的数字由小到大依次产生,每个数字出现的次数为 [0,+∞)[0,+\inf ...
2021牛客暑期多校3 B.Black and white
题目大意
给定一个矩阵ccc,初始每个格子都是白色的,可以花费c[i][j]c[i][j]c[i][j]的代价将i,ji,ji,j位置染成黑色,特殊的,如果行i,ji,ji,j和行k,hk,hk,h满足mat[i][k],mat[i][h],mat[j][k]mat[i][k],mat[i][h],mat[j][k]mat[i][k],mat[i][h],mat[j][k]都是黑色,那么mat[j][h]mat[j][h]mat[j][h]可以消耗000的代价直接染成黑色。求将整个矩阵染黑的最小花费。
思路
这道题在赛中就有了考虑,保证每行每列都有一个黑色,然后在任何一个其他地方安放一个黑色即可将所有位置涂黑,也想了一些方法来做这道题,但是都没有过去,赛后看了题解才恍然大悟。
正如赛中的考虑,将每行抽象成一个点,编号 [1,n][1,n][1,n],将每列抽象成一个点,编号 [n+1,n+m][n+1,n+m][n+1,n+m],对于 mat[i][j]mat[i][j]mat[i][j] 涂黑可以定义为在 i,n+ji,n+ji,n+j 点之间连接一条边,那么整个题目就可以抽象成一个 ...
2021牛客暑期多校2 B.Cannon
题目大意
有一个棋盘只有两行,但有 10100010^{1000}101000 列,第一行上有 xxx 个炮,第二行上有 yyy 个炮。
众所周知,中国象棋中炮吃一个子时需要中间有一棋子作为炮架。记发生 kkk 次炮吃炮事件的方案数 (mod109+9)\pmod{10^9+9}(mod109+9) 为 fkf_kfk,输出 ⨁k=0x+y−4fk\bigoplus\limits_{k=0}^{x+y-4}f_kk=0⨁x+y−4fk。题目需要输出两个答案,分别对应两个限制条件:1.不考虑两行发生事件的顺序;2.事件必须先在第一行发生,之后再在第二行发生,不能再返回第一行发生。
思路
对于某一行上共 rrr 个炮,考虑哪一个炮作为炮架,产生一次炮吃炮事件的方案数为 2(r−2)2(r-2)2(r−2);因此,产生 ttt 次炮吃炮事件的方案数为 2(r−2)×2(r−1−2)×⋯×2(r−t+1−2)=2t(r−2)!(r−2−t)!2(r-2)\times 2(r-1-2)\times\cdots\times 2(r-t+1-2)=2^t\frac{(r-2)!}{(r-2-t ...