11D_Beyonder's Blog

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)∫ab​f(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)∫ab​f(x)dx≈k=0∑n​Ak​f(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​+a1​x，使总误差最小。记 ...

问题描述 不考虑出生年份，一个房间中至少多少人，才能使其中两人生日相同的概率达到 $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简介 明文 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 ...

题目大意 玩一场游戏，每一轮在 [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∑n​wj​wi​​。 思路 游戏生成的数字序列一定是类似 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 ...

题目大意 给定一个矩阵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 点之间连接一条边，那么整个题目就可以抽象成一个 ...

题目大意 有一个棋盘只有两行，但有 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−4​fk​。题目需要输出两个答案，分别对应两个限制条件：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 ...