今天打 51nod 的比赛打自闭了，打满暴力就去水 uoj 群，发现有人问这题，突然发现自己只会组合型的母函数，这种还要搞排列的不会 qwq，所以就来学了学。
其实参考一个课件就行了
所谓有重复元素的排列，设元素种类为 $n$，第 $i$种颜色有 $k_i$个，显然排列方法有
$$\frac{n!}{\prod (k_i!)}$$
比如说 $n=5$，$k_1=2,k_2=3$
取 $4$个元素的排列方法就有
$$\frac{4!}{1!3!+2!2!}$$
于是我们想到构造一个母函数
$$F(x)=(1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots)$$
上面那个栗子就是
$$F_1(x)=(1+\frac{x^1}{1!}+\frac{x^2}{2!})$$
$$F_2(x)=(1+\frac{x^1}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!})$$
上面这两个式子卷积，显然 $x^4$的系数就是
$$\frac{1}{1!3!+2!2!}$$
然后乘一个 $4!$就行了。
对于 $poj$这道题，我们显然可以写出它的母函数
$$F(x)=(1+\frac{x}{1!}+\frac{x^2}{2!}+\cdots)^2(1+\frac{x^2}{2!}+\frac{x^4}{4!}+\cdots)^2$$
你可以暴力枚举四个式子的系数然后用广义多项式算，然而这肯定超时了
考虑转化成母函数的闭形式化简
因为 $e^x$的泰勒展开为
$$e^x=(1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots)$$
带进去
$$F(x)=(e^x)^2(\frac{e^x+e^{-x}}{2})^2$$
化简
$$F(x)=\frac{e^{4x}+2e^{2x}+e}{4}$$
再带回来知道 $x^n$的系数为
$$\frac{4^{n-1}+2^{n-1}}{n!}$$
所以 $4^{n-1}+2^{n-1}$就是答案了
代码太简单不贴了
0 条评论