nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
先考虑一个简单的问题
$$f(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor$$
阅读全文
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
公式$$g(1)\sum_{i=1}^nf(i)=\sum_{i=1}^{n}(f*g)(i)-\sum_{d=2}^{n}g(d) \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)$$
使用很多时候我们会碰到求积性函数前缀和的情况，由于积性函数的前缀和不一定依然是积性函数，所以我们需要使用一些技巧。
比如给你一个积性函数$f(x)$, 现在要求你计算$\begin{aligned}\sum_{i=1}^n f(x)\end{aligned}$。
阅读全文
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
简介快速幂是能快速计算一个幂的方案，他可以作用于所有满足结合律、封闭性的二元运算，即半群
定义不妨假设这个二元运算为$\circ$,两个元素进行运算为$x\circ y$,当$xy$同为$x$时，不妨设$x^2=x\circ x$, 同样的$x^1=x$, 当然$x^0=e$, 还有$x^k=x^{k-1}\circ x$
快速幂核心思想在半群中，只要$k=u+v$一定有$x^k=x^u\circ x^v$.
所以我们可以把k看作一个二进制数，把$x^k$分解为$x^{2^{p_1}}\circ x^{2^{p_2}}\circ x^{2^{p_3}}\circ \circ \circ x^{2^{p_n}}$
这里最多分解为$\log_2(k)$个元素，而且每个元素可以由前k个元素获取，所以只需要进行$log_2(k)$次二元计算即可的到最终答案。
阅读全文
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
介绍球盒模型指的是把球放入盒子里的题目模型（强行解释）
分为盒子同或不同，球同或不同，盒子允许空或不空，所以一共八种问题
结论不妨假设n个球，m个盒子
盒异，球同，盒子允许空 $C_{m+n-1}^{m-1}$
盒异，球同，盒不允许空$C_{n-1}^{m-1}$
盒同，球同，盒子允许空$\begin{aligned}\prod _{j=1}^{m}\frac{1}{1-x^{j}}\end{aligned}$中的$x^n$系数
盒同，球同，盒不允许空$\begin{aligned}x^m\prod _{j=1}^{m}\frac{1}{1-x^{j}}\end{aligned}$中$x^n$的系数
盒异，球异，盒子允许空 $m^n$
盒异，球异，盒不允许空$\begin{aligned}\sum _{k=0}^{m}(C_m^k(-1)^{m-k}k^n)\end{aligned}$
盒同，球异，盒子允许空$$\begin{aligned}\sum_{i=0}^{m} \sum_{k=0}^i\frac{C_i^k(-1)^{i-k}k^n}{i!}\end{aligned}$$
盒同，球异，盒不允许空$\begin{aligned}\sum _{k=0}^m\frac{C_m^k(-1)^{m-k}k^n}{m!}\end{aligned}$
阅读全文