传送喵

今天打 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}$就是答案了

代码太简单不贴了

分类: 文章

quhengyi11

AFO 有缘再见

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注