2022.7.23补

C

要求出现至少c_i次不太好限制,考虑用gf表示一下,就是

\sum_{j\geq c_i}\frac{x^j}{j!}

那么答案就是

n![x^n]\prod_{i}^{w-1}\sum_{j\geq c_i}\frac{x^j}{j!}=n![x^n]\prod_i^{w-1}(e^x-\sum_{j\geq 0}^{c_i-1}\frac{x^j}{j!})

因为n\leq 10^7,所以不好直接做多项式乘法,但是e^x的展开可以被简单计算,尝试对e^x和与c_i相关的系数分离

考虑换元,令e^x=A

设前k次乘法形成的复合多项式为

F=B_0+B_1A+B_2A^2+...

k+1次附与(A+g_{k+1})的乘法,其中g_k=-\sum_{j\geq 0}^{c_k-1}\frac{x^j}{j!},即

F'=B_0g_{k+1}+(B_0+B_1g_{k+1})A+(B_1+B_2g_{k+1})A^2+...

那么最后形成的多项式为\sum_{i\geq 0}^{w}e^{ix}F_i(x)的形式

对于每个k\leq w, 需要在A^i,i\leq w的系数处做一次ntt,故一共需要做w^2次ntt,并且每次ntt的上界\leq \sum_i c_i=5e4

考虑询问n时候的答案怎么求,因为是复合,所以需要枚举x^j的指数,之前多项式F_i(x)已经求出,设当前x^j,那么对应e^{ix}展开式指数为n-j,系数为\frac{i^{n-j}}{(n-j)!},所以答案为

n!\times\sum_{i=0}^w\sum_{j=0}^{\min{(n,|F_i|)}}[x^j]F_i(x)\frac{i^{n-j}}{(n-j)!}

这破题有卡常嫌疑

组合计数 多项式 生成函数

教务处和后勤
上一篇 «
2022.7.23 nc-2 补
» 下一篇
© 2017 - 2024 云雀.
...... visits · ...... visitors