Dirichlet

 ![](https://img2023.cnblogs.com/blog/2702872/202312/2702... ......

历史 相关概念 概念 三维狄利克雷分布 原理 作用 ......

[传送门](https://www.luogu.com.cn/problem/P5495) 求$b_k=\sum\limits_{i|k}{a_i}$ 考虑$i=p_1^k,j=p_1^{k+1}$，若我们已经求出了$b_i$，则易知$b_j=b_i+a_j$ 然后根据上面的方法，考虑对于所有的$k ......

# Dirichlet学习笔记 ## Dirichlet前缀和 狄利克雷前缀和是求解形如 $$ b_k=\sum\limits_{i|k}a_i $$ 的式子 首先我们可以想到枚举 $i$ ，再枚举 $i$ 的倍数 $j$ $$b_j=b_j+a_i$$ 此时的时间复杂度为 $n/1+n/2+n/3 ......

遇到一个要使用 dirichlet 分布的情形，发现 C++ 标准库中没有现成的。查阅维基百科发现，虽然它挺复杂，但是它跟 Gamma 分布有如下关系： 设有 K 个相互独立且分别满足 Gamma 分布的分布： $$Y_1 \sim Gamma(\alpha_1, \theta), ..., Y_K ......