HDU 6116 路径计数
普通生成函数常用于处理组合问题,指数生成函数常用于处理排列问题。
考虑 对于a个A分为很多堆,这么分的方案数是Ci−1a−1
然后对于每一堆我们看成一个数来放,并且所有堆都这样做,这样的话总的方案数量是(i+j+k+l)!i!j!k!l!
就算所有一堆看成的数的排列是不存在相邻相等的,至少都有n−i−j−k−l对相邻的相同的数。
然后就可以容斥了,枚举i+j+k+l直接计算就好了。
ans=n∑x=1(−1)n−xx!∑i+j+k+l=xCi−1a−1Cj−1b−1Ck−1c−1Cl−1d−1i!j!k!l!
后面其实就是四个指数生成函数乘积了。
cpp
1 |
|