zcmimi's blog

arrow_back生成函数共8篇文章

avatar
zcmimi
2020-06-25

推荐:

定义

生成函数又称母函数

设序列aa_0,a_1,a_2,\dots

avatar
zc
2020-09-15 20:16:00
查看原题

点击跳转

g(n)为点数为n的无向图个数

g(n)=2^{n\choose 2}

f(n)为点数为n的简单无向连通图的数量

枚举连通块个数i可得

\displaystyle g(n)=\sum_{i=0}^n \frac{f(i)}{i!}

发现这个形式很眼熟(生成函数):

g=e^f

那么f=\ln g

求出g\ln就可以得到f

avatar
zc
2020-07-09 21:41:00
查看原题

点击跳转

拆分为m项时,生成函数为F^m (x)

那么答案的生成函数为\displaystyle G(x)=\sum_{i=0}^{\infin} F^i(x)

F为斐波那契数列生成函数,\displaystyle F(x)=\frac x{1-x-x^2}

\begin{aligned} G(x) &=\sum_{i=0}^{\infty} F^i(x)\\ &=\frac 1{1-F(x)}\\ &=\frac {1-x-x^2}{1-2x-x^2}\\ &=1+\frac x{1-2x-x^2}\\ &=1+\frac x{[1-(1+\sqrt 2)x][1-(1-\sqrt2)x]}\\ &=1+\frac 1{2\sqrt 2}\left( \frac 1{1-(1+\sqrt 2)x} - \frac 1{1-(1-\sqrt 2)x} \right)\\ &=1+\sum_{i=1}^{\infin} \frac{(1+\sqrt 2)^i-(1-\sqrt 2)^i}{2\sqrt 2} x^i \end{aligned}

那么:

\displaystyle ans_n=\frac{(1+\sqrt 2)^n-(1-\sqrt 2)^n}{2\sqrt 2}

其中\sqrt 2 \equiv 59713600 \pmod{10^9+7}(二次剩余)

这样的话:

\displaystyle \begin{aligned} ans_n &=\frac {\sqrt 2}4\left[(1+\sqrt 2)^n-(1-\sqrt 2)^n\right]\\ &\equiv 59713600\times 250000002\times [(1+59713600)^n-(1-59713600)^n] \pmod{10^9+7} \end{aligned}

使用快速幂复杂度O(\log n)

考虑费马小定理: ans_n \equiv ans_{n \mod 10^9+6}

这样就可以把n压到10^9+6以内了,再快速幂即可

avatar
zc
2020-07-07 17:25:00
查看原题

点击跳转

首先了解原根

这里利用到原根的一个性质:

gm的一个原根
g^0,g^1,g^2,\dots,g^{\varphi(m)-1}构成模m的简化剩余系

这样我们可以把序列中所有数变成原根的次幂,

那么序列中所有数的乘积就可以转化为他们的和

设这个和为sum

设生成函数:\displaystyle f(x)=\sum_{i=0}^m [i\in S]x^i

可以发现f(x)^n次数为sum的那一项的系数就是答案

使用快速幂+快速数论变换

avatar
zc
2020-02-07 13:50:00
查看原题

点击跳转

  1. 金神石的块数必须是6的倍数 g(x)=1+x^6+x^{12}+...=\frac 1{1-x^6}
  2. 木神石最多用9块 g(x)=1+x+x^2+...+x^9=\frac{1-x^{10}}{1-x}
  3. 水神石最多用5块 g(x)=1+x+x^2+...+x^5=\frac{1-x^6}{1-x}
  4. 火神石的块数必须是4的倍数 g(x)=1+x^4+x^8+...=\frac 1{1-x^4}
  5. 土神石最多用7块 g(x)=1+x+x^2+...+x^7=\frac{1-x^8}{1-x}

  6. 金神石的块数必须是2的倍数 g(x)=1+x^2+x^4+...=\frac 1{1-x^2}

  7. 木神石最多用1块 g(x)=1+x=\frac{1-x^2}{1-x}
  8. 水神石的块数必须是8的倍数 g(x)=1+x^8+x^{16}+...=\frac 1{1-x^8}
  9. 火神石的块数必须是10的倍数 g(x)=1+x^{10}+x^{20}+...=\frac 1{1-x^{10}}
  10. 土神石最多用3块 g(x)=1+x+x^2+x^3=\frac{1-x^4}{1-x}

\frac 1{1-x^6}\cdot\frac{1-x^{10}}{1-x}\cdot\frac{1-x^6}{1-x}\cdot\frac 1{1-x^4}\cdot\frac{1-x^8}{1-x}\cdot\frac 1{1-x^2}\cdot\frac{1-x^2}{1-x}\cdot\frac 1{1-x^8}\cdot\frac 1{1-x^{10}}\cdot\frac{1-x^4}{1-x}

=\frac1{(1-x)^5}

=\sum_{i=0}^\infty {i+4 \choose 4}x^i

\sum_{i=0}^\infty {i+k-1 \choose k-1}x^i=\frac1{(1-x)^k}

n项的系数是{n+4 \choose 4}需要FFT或NTT

avatar
zc
2020-01-22 22:57:00
查看原题

点击跳转

f_n表示n个节点可以构成的二叉树的个数,g_n表示n个节点可以构成的二叉树的叶子节点的总数

打表: 可以发现g_n=nf_{n-1}

证明: 对于每棵有n个节点的二叉树,若它有k个叶子节点,删去后可以得到kn-1个节点的二叉树,而这kn-1个节点的二叉树每棵都有n个位置可以放置新的叶子节点

f_1=1\\ f_n=\sum_{i=1}^{n-1}f_if_{n-i-1}

f其实就是卡特兰数

代入ans=\frac{g_n}{f_n}得到\frac{n(n+1)}{2(2n-1)}

avatar
zc
2020-01-22 17:49:00
查看原题

点击跳转

g(x)=(1+x+x^2+x^3+...+x^{num_1})(1+x^2+x^4+...+x^{2num_2})(1+x^5+x^{10}+x^{15}+...+x^{5num_3})

avatar
zc
2020-01-22 17:05:00
查看原题

点击跳转

g(x)=(1+x+x^2+x^3+...)(1+x^2+x^4+x^6+...)(1+x^3+x^6+x^9+...)...

模拟一下

\Theta(n^2)

1/1
Search
search