LOJ 6503

Solution :

某题(luogu 4448)的加强版

定义权值对合法,那么就是求恰好满足k个条件的方案数,容斥转化成求至少k个条件,考虑权值为k的排列怎么构造。

显然对于长度为x的相同连续排列,权值为x-1,如果是两个长度分别是x,y的相同连续块,中间(可能被)其他块分隔开来,那么就会产生至少x+y-2的权值。因为我们限定了连续块大小,所以一定会产生x+y-2的权值,因为中间可能没有其他块(随机排列),所以可能会产生+1的权值,因此完成了至少的目标。

设第i种牌有m_i张,我们知道每切割一次,权值就会降低1,现在有m_i-1的权值,目标是产生x_i的权值,那么应该切割m_i-x_i-1次(即把当前序列切割成m_i-x_i块),直接插板得到系数为\binom{m_i-1}{m_i-x_i-1},对于luogu的弱化版,因为每个元素都有区别,所以需要再带一个m_i!;对于多个元素来说全排列变为多项式系数,设产生至少\alpha权值的序列方案数为g(\alpha),那么答案g(\sum_i x_i)即为

\frac{(\sum_{i}m_i-x_i)!}{\prod_{i}(m_i-x_i)!}\prod_i\binom{m_i-1}{m_i-x_i-1}

因为不确定对于答案的具体组成(即本质序列(x_1,x_2...x_m)不同下的具体贡献),考虑\rm dp钦点

g_{i,j}表示考虑前i种牌至少有j权值贡献的方案数,直接枚举最后一种牌的贡献即可,转移为

\begin{aligned} \frac{g_{i,j}}{(n-j)!}&=\sum_{k=0}^{\min(j,m_i)}g_{i-1,j-k}\frac{1}{(m_i-k)!}\binom{m_i-1}{m_i-k-1}\\ &=\sum_{k=0}^{\min(j,m_i)}g_{i-1,j-k}\frac{1}{(m_i-k)!}\binom{m_i-1}{k} \end{aligned}

换个角度理解的话背包划分跟\rm EGF乘法没有特别大区别,设G(x)=\sum_{j\geq 1}^{m_i}x^j\frac{1}{(m_i-j)!}\binom{m_i-1}{j},那么对应的[x^j]就是权值为j的方案数,多个\rm EGF卷起来即可(这里写反了自己注意一下)。

考虑怎么合并m个总长度为n的多项式

暴力做m\rm NTT复杂度爆炸,考虑启发式合并,每次取出两个最短的做启发式合并即可,那么每个最多会被合并O(\log)次,复杂度O(m\log^2n)

做完之后再容斥回来,别忘了带(n-j)!的额外系数

组合计数 生成函数 dp NTT 启发式合并

Min25笔记
上一篇 «
2022.10.10补
» 下一篇
© 2017 - 2024 云雀.
...... visits · ...... visitors