二项式反演
二项式反演 对于某些问题，比较容易计算 钦定 \(k\) 个位置的可能性 而比较难计算 有 \(k\) 个位置的可能性 这个时候可以用二项式反演对问题进行转化 形式2 一共有 \(n\) 个元素，设 \(f(k)\) 是钦定 \(k\) 个元素的方法数，\(g(k)\) 是恰好选 \(k\) 个元素的方法数，那么有如下关系 \[ f(k) =\sum_{i=k}^n\left(\begin{array}{l}i \\k\end{array}\right) g(i) \Leftrightarrow g(k) = \sum_{i=k}^n (-1)^{i-k}\left(\begin{array}{l}i \\k\end{array}\right) f(i) \] 每个 \(g(i)\) 有 \(\left(\begin{array}{l}i \\k\end{array}\right)\) 种钦定方法 例子 \((a,b,c,d)\) 中求 \(f(2)\) 和 \(g(2)\) 钦定 \((a,b)\) , \((a,c)\), \((a,d)\) , \((b,c)\) ...
硬件安全
硬件安全 安全的定义 Create, maintain and attest a secure state for an embedded device Ensure confidentiality, integrity and availability of the data processed on the device Ensure the safety of the people and the environment interacting with the device Protect the device itself, its environment and other data from processed malicious data Abstraction Layers and Attack Vectors skipped Secure Embedded System Design Typical Criteria Time to market Design + manufacturing setup cost Component + manufact...
模拟电子技术
模拟电子技术 本征半导体 本征半导体是纯净的具有晶体结构的半导体。 载流子：运载电荷的粒子称为载流子。导体导电只有一种载流子, 即自由电子导电; 空穴：当电子挣脱共价键的束缚变成为自由电子后，在共价键中留下一个空位置，称为空穴
密码学
密码学 理论基础 Alice 给 Bob 发消息，保护消息的 confidentiality. 传输途径可以是任意的，Internet, USB stick… 在过程中被动的监听者Eve 有可能会监听或者解释信息. 在过去，军事加密依赖于信息的混乱程度 obfuscation of message contents. 现代密码学依赖于 Kerckhoff’s Principle, 除了key所有信息都是已知的. A crypto system should be secure, even if everything about the system, except the key, is public knowledge. 信息加密是通过 encryption schemes 使用一个key和lock concept来实现的. 只有key的持有者可以加密解密信息. Alice会把key \(k\) 分享给Bob, 我们现在还不关系这个怎样实现. Alice 加密信息 \(m\), \(c := E(k,m)\) Bob 解密信息 \(m:=D(k,c)\) 香农密码 Sh...
高效算法II
高效算法II 线性规划(LP) Standard Form input: number \(a_{ij},c_j,b_j\) output: numbers \(x_j\) \(n = \#decision variables, m=\#conatrains\) \(\begin{aligned} & \max \sum_{j=1}^n c_j x_j \\ & \text { s.t. } \sum_{j=1}^n a_{i j} x_j=b_i \quad 1 \leq i \leq m \\ & x_j \geq 0 \quad 1 \leq j \leq n \\ & \end{aligned}\) 也可以用矩阵的写法 \(\begin{array}{rr}\max & c^T x \\ \text { s.t. } \quad A x=b \\ & x \geq 0\end{array}\) 转换成Standard Form 小于等于 \(a-3b+5c\le 12\) 变成 \(a-3b+5c+s=12,s \ge 0...
客制化键盘设计
客制化键盘设计 设计布局 这个网站 可以在线设计布局，设计完成之后可以复制 Raw Data 来进行下一步。 image-20230419164533764 123456["Esc",{x:1},"F1","F2","F3","F4",{x:0.5},"F5","F6","F7","F8",{x:0.5},"F9","F10","F11","F12",{x:0.25},"PrtSc","Scroll Lock","Pause\nBreak"],[{y:0.5},"~\n`","!\n1","@\n2",...
统计学基础
统计学基础 Varianece 方差 运算法则 \[ Var(aX+bY)=a^2Var(X)+b^2Var(Y)+2abCov(X,Y) \] \[ \operatorname{Var}(Y)=\operatorname{Var}(a X+b)=a^{2} \operatorname{Var}(X) \] Corvariance 协方差 对于两个随机变量 \(X_1,X_2\) \[ \operatorname{Cov}\left(X_{1}, X_{2}\right)=E\left(\left(X_{1}-\mu_{1}\right)\left(X_{2}-\mu_{2}\right)\right) \] 另一个等价的公式 \[ \operatorname{Cov}\left(X_{1}, X_{2}\right)=E\left(X_{1} X_{2}\right)-\mu_{1} \mu_{2} \] 若两个随机变量 \(X_1, X_2\) 是独立的 \[ \operatorname{Cov}\left(X_{1}, X_{2}\right)=0 \] 有一个数据集的两个...
刷题总结DIV1C
知识点 枚举 cnt枚举2个量 在一个数组中, \(cnt[x]\) 代表 \(x\) 出现的次数 \[ \sum_x cnt[x] \le n \] 于是可以枚举所有 \(x\) 在枚举所有小于 \(cnt[x]\) 的数，总复杂度不超过 \(O(n)\) CF1637E(2100) 枚举 \(2^k\) 长度是 \(2^k\) 那么直接枚举 \(k\) 即可 CF1626D(2100) 二分 同时检查多个参数: 用二进制表示，0表示不符合，1表示符合，放到一个集合里，再枚举集合 zone2021_c 对 $x_i \(找下一个不超过\)L$ 的点，可以用lowerbound查询 倍增dp arc060_c 整体二分 CF1601C 并查集 对于两者选1的问题，用边建图，然后分析。 arc111_b 数据结构，小的向大的合成可以降低复杂度 abc183_f 神奇构造 分式 \[ \frac{1}{x(x+1)} = \frac{1}{x} - \frac{1}{x+1} \] arc163c 拆分再组合 agc055_a 构造部分解，然后组合...
非线性优化
问题设置 一般的非线性优化问题 \[ \min _{x \in \mathbb{R}^{n}} f(x) \quad \text { s.t. } \quad g(x) \leq 0, \quad h(x)=0 \] \(f\) 是目标函数，连续可导 \(g\) 是\(m\) 个不等号约束条件 \(h\) 是 \(p\) 个等号约束条件 定义1 feasible set 集合 \[ X=\left\{x \in \mathbb{R}^{n} ; g(x) \leq 0, h(x)=0\right\} \] 是feasible set (可行的集合), \(x\) 是 feasible 若它在这个集合中。index set of active inequality constraints \(\mathcal{A}(x)\) 是在不等式中使得等号成立的集合。\(\mathcal{I}(x)\) 是不等号严格成立的集合 \[ \begin{aligned} &\mathcal{A}(x)=\left\{i ; 1 \leq i \leq m, g_{i}(x)=0\right...
线性规划
线性规划问题 我们要优化一个目标函数 \[ F(x_1,x_2,...x_p)=c_1x_1 + c_2x_2+...+c_px_p \] 也就是求它的最大值或者最小值。同时还有很多约束条件 \[ a_{i1}x_1+...+a_{ip}x_p \le b_i \\ a_{i1}x_1+...+a_{ip}x_p \ge b_i \\ a_{i1}x_1+...+a_{ip}x_p = b_i \] 以及非负的限制条件 \[ x_j \ge 0 \] 解集的定义 \(\textbf{x}=(x_1,x_2,...,x_p)\) 满足线性约束条件的是一个解 如果 \(\textbf{x}\) 还满足非负限制条件，那么是一个可行解 \[x^{*}\] 是最优解 \[X^*\] 是所有最优解的集合 转化问题 每个线性规划问题可以转化成最大值的线性规划问题： 最大化目标函数 \[ F(x_1,x_2,...x_p)=c_1x_1 + c_2x_2+...+c_px_p \] 约束条件： \[ \sum_{j=1}^{p} a_{ij} x_j \le b_i \\ x_j ...