https://wiki.cvbbacm.com/ 2026-04-30T03:57:19+0800 https://wiki.cvbbacm.com/ https://wiki.cvbbacm.com/lib/exe/fetch.php?media=favicon.ico text/html 2020-05-28T08:34:33+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:no_morning_training:shaco:%E7%9F%A5%E8%AF%86%E7%82%B9:%E6%95%B0%E8%AE%BA:%E7%94%9F%E6%88%90%E5%87%BD%E6%95%B0&rev=1590626073&do=diff 生成函数 前言 用以解决一类问题:几类物品各自可以取的数目具有一定的限制，求共取i种的方案数。 概念 对于数列$a_{n}=\{a_1,a_2,···,a_n\}$，它的生成函数即为$f(x)={a_1x+a_2x^2+···+a_nx^n}$。 常见类型 这里介绍的是一种将x限定在(-1,1)的范围内化简的结果（x本身也没有意义，可以添加一些设定），这样的简化结果利于后面的计算，而且与不化简的记过表达的意义是相同的。 \[\sum_{i=0}^{\infty}{x^{ik}}=\frac{1}{1-x^k}\]\[\sum_{i=0}^{n}{x^{ik}}=\frac{1-x^{(n+1)k}}{1-x^k}\]\[\sum_{i=0}^{\infty}{C_{i+k-1}^{k-1}}{x^i}=\frac{1}{(1-x)^k}\]$x^i$$\frac{1}{1-x^2}$$\frac{1}{1-x^5}$$\frac{1-x^5}{1-x}$$(1+x)$$\frac{1}{(1-x)^2}$$1+2x+3x^2+···$… text/html 2020-05-15T21:07:15+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:no_morning_training:shaco:%E7%9F%A5%E8%AF%86%E7%82%B9:%E6%95%B0%E8%AE%BA:%E7%AD%9B%E6%B3%95&rev=1589548035&do=diff 筛法 确定素数。 埃氏筛 思想 从每个素数出发，将其倍数都筛掉。 性能 每一个合数会被访问多次；复杂度$O(nloglogn)$。 代码 for(int i=2;i<=maxn;i++) { if(!vist[i]) for(int j=i*i;j<=maxn;j+=i) vist[j]=1; } $O(n)$ text/html 2020-05-15T21:07:34+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:no_morning_training:shaco:%E7%9F%A5%E8%AF%86%E7%82%B9:%E6%95%B0%E8%AE%BA:front_page&rev=1589548054&do=diff 筛法