Blog E

路漫漫其修远兮，吾将上下而求索。

Improved Decoding of Expander Codes 学习笔记

原论文： Xue Chen, Kuan Cheng, Xin Li, and Minghui Ouyang. 2023. Improved Decoding of Expander Codes. IEEE Trans. Inf. Theor. 69, 6 (June 2023), 3574–3589. https://doi.org/10.1109/TIT.2023.3239163 The size-expansion tradeoff Thm. Any $(\alpha N,(1-\varepsilon D)$ expander is also roughly a $(k \al...

Posted by ethan-zhou on July 20, 2024

X265 码率控制算法

参考资料：https://www.cnblogs.com/lakeone/p/5436481.html 关于算法部分写的很清晰 1-PASS ABR rateControlStart() 这个函数相当于码率控制的入口，会在每一帧被编码前调用，根据码率控制设置编码参数。 double q = x265_qScale2qp(rateEstimateQscale(curFrame, rce)); ... rateEstimateQscale(curFrame, rce) ABR 码率控制模式的主要函数，设定当前帧的 QScale B 帧没有单独进行码率控制，其 QP 是通...

Posted by ethan-zhou on July 18, 2024

2024WF游记

好像能进 9 月哈萨克斯坦的 World Final 了，这学期没怎么训，假期打算开始复健，于是打算先写个游记占坑。 7.1 有场 div 1+2，因为大号 @ethan_enhe 三月刚上红，不太敢动。遂创小号 @_furina 开打。没想到打得还不错，rnk 99，猛加 867 rating。 发现法国 cf 不太行，于是把小号地址设到了法国（符合原著），打算看看能不能打到前三。至高无上的水神陛下即将抵达自己忠实的枫丹！ 7.7 拿小号去 div2 炸鱼了，题都会，可惜差一题没写出来, rnk 5。 这比赛怎么这么多猜结论题。。。 7.15 拿小号去 div2 炸...

Posted by ethan-zhou on July 4, 2024

LSPN论文调研

终于把大研的中期报告胡过去了，听说没有人看，于是就写的简单点。 正好也好久没发博客，就把文献调研部分拿出来发一个，记录一下这学期读的部分文章。因为大研报告的提交平台的富文本编辑器不支持公式，所以这里也就都没有用 latex，凑合看吧[doge] 研究问题 Learing Parity with Noise 的问题描述如下： 有一个隐藏的，长度为 n 的 0/1 向量 s, 目标是找出它 我们可以对数据库进行若干次询问，每次询问，会得到如下的回答： 一个长度为 n 的随机 0/1 向量 y x dot y mod 2 的结果（但是会以 e...

Posted by ethan-zhou on June 10, 2024

Probability and Computing 第九章笔记

单变量正态分布 Moment Generating Function \[M_X(t)=e^{t^2\sigma^2/2+\mu t}\] Chernoff bound \[\Pr(\|\frac{X-\mu}{\sigma}\|\ge a)\le 2e^{-a^2/2}\] 中心极限定理 二项分布的极限 n 充分大时，$B(n,p)$ 的概率分布趋近于与其同方差与均值的正态分布。 中心极限定理 $X_1,X_2\cdots X_n$ 独立同分布，则： \[\lim_{n\rightarrow \infty}\Pr(a\le \frac{\overline X-\mu...

Posted by ethan-zhou on February 11, 2024

Probability and Computing 第八章部分习题

Posted by ethan-zhou on February 3, 2024

Probability and Computing 第八章笔记

泊松过程——最独立的一集

这一章节前面不少内容偏概念，和概统课讲的一样，下面主要记录泊松过程和连续马尔可夫过程分布的一些性质，泊松分布给我的直观感受就是，什么统计量之间都是独立的。 Balls and bins with feedback 两个 bin，分别有 x，y 个球的时候，再来一个球，以 $\frac {x^p}{x^p+y^p}$ 的概率进入第一个 bin，剩下概率进入第二个 bin。初始 $x=y=1$ $p=1$ 时，n 轮之后 x 均匀分布 $p>1$ 时，with probability 1 there exist a number c such that one...

Posted by ethan-zhou on February 3, 2024

Probability and Computing 第七章部分习题

算不动了

写了部分习题, upd. 最后一题的放缩问了个同学，现在会了，大致是把递推式放缩成 $i(f_i-f_{i-1})\le (n-i)(f_{i+1}-f_i)$，后面懒得写了。

Posted by ethan-zhou on February 1, 2024

Probability and Computing 第七章笔记

突然发现，上次发博客还是上次了，因此，我打算打算一下，简单写个笔记记录一下这章内容。 Notation $r^t_{i,j}$: 从i开始走，t时刻恰好第一次到j的概率 $h_{i,j}$: 从i开始走，第一次到j的期望步数 Definition 略 Classification of States 连通性 accessible: $\exist n,\text{ s.t.} P^n_{i,j}>0$ communicate: i,j 双向联通 若整个链是一个 communicating class / 对应的图强连通，则称其 irreducible...

Posted by ethan-zhou on January 4, 2024

Probability and Computing 第五章作业题

题目 模拟代码（第二问） bool f[MXN]; #define ls(x) ((x) << 1) #define rs(x) (((x) << 1) | 1) #define bro(x) ((x) ^ 1) #define fa(x) ((x) >> 1) queue<ll> q; ll n, cnt; ll chk(ll r) { ll cnt = (ll)f[r] + f[ls(r)] + f[rs(r)]; if (cnt == 2) { if (!f[r]) return r; ...

Posted by ethan-zhou on September 7, 2023

FRIENDS

ABOUT ME

avatar

一个 OIer ICPCer，喜欢弹吉他，踢球，爱好编程

✉️ zehzhou [at] mail [dot] ustc [dot] edu [dot] cn

FEATURED TAGS

算法 游记 前端 线段树 题解 USACO dp 图论 xcpc 随机算法
icon