首页 > 编程学习 > 准大二~准大三开摆记录

准大二~准大三开摆记录

发布时间:2022/8/12 13:49:07

22.08.12

上午给小朋友入门了一下组合计数,感觉把他们讲自闭了

Problem 1

\(T\)\(k\)\([x^k]\frac {P(x)}{\prod\limits_{i=1}^m(1-a_ix)^{b_i}},\deg P\le\sum\limits_{i=1}^mb_i\le n\)

直接线性递推后面部分为 \(O(Tn\log k \log n)\),这里可以通过分式分解做到 \(O(n\log^2n+Tn)\)

首先可以看成拆分为 \(m\) 种线性递推,即写成 \([x^k]\sum\limits_{i=1}^n\frac{P_i(x)}{(1-a_ix)^{b_i}}\)

反向考虑 \(CRT\) 的过程,即得 \(P_i(x)=(P(x)\mod (1-a_ix)^{b_i})*(\frac1{\prod\limits_{j\not=i}(1-a_jx)^{b_j}}\mod (1-a_ix)^{b_i})\)

考虑建立分治树,对于区间 \([l,r]\) 维护 \(Mod_{l,r}=\prod\limits_{l\le i\le r}(1-a_ix)^{b_i}\)
那么前面部分就是用 \(P\) 从根多项式取模到叶子;后面部分可以先不考虑求逆,而是求 \(\prod\limits_{j\not=i}(1-a_jx)^{b_j}\mod(1-a_ix)^{b_i}\)。现在在分治树上走,记一个多项式 \(f\),在根处 \(f=1\),向左子树走的时候 \(f\leftarrow f*Mod_{mid+1,r}\mod Mod_{l,mid}\),向右子树走的时候 \(f\leftarrow f*Mod_{l,mid}\mod Mod_{mid+1,r}\)。到达叶子后,需要计算 \(f(x)\mod (1-a_ix)^{b_i}\),不妨记 \(g(x)=f(\frac{1-x}{a_i})\mod x^{b_i}\),那么 \(f\rightarrow \frac1{g(x)}\mod x^{b_i},f(x)\leftarrow f(1-a_ix)\) 就解决了。

求出 \(P_i(x)\) 后,我们还需求出每个 \([x^k]\frac{P_i(x)}{(1-a_ix)^{b_i}}\),暴力 \(O(\deg P_i(x))\) 计算就好了。

Copyright © 2010-2022 ngui.cc 版权所有 |关于我们| 联系方式| 豫B2-20100000