abc285h题解
2024-10-21 19:38:13
考虑容斥,强制要求\(k\)个数为完全平方数,系数为\((-1)^k*C_n^k\)(因为我们要从\(n\)个数选出\(k\)个数作为完全平方数)。则在唯一分解\(p_1^{e_1}...p_n^{e_n}\)中,\(e_1...e_n\)都必须是偶数。
对于每个质因数分开考虑,答案是每个质因数的答案的乘积。
一个没有要求的数的OGF是\(\frac{1}{1-x}\),一个被钦定为完全平方数的数的OGF是\(\frac{1}{1-x^2}\)
我们要求\(F(x)\frac{1}{(1-x)^{n-k}}\frac{1}{(1-x^2)^{k}}[x^{e_{1...n}}]\),可以把\(\frac{1}{(1-x)^{n-k}}\frac{1}{(1-x^2)^{k}}\)展开后求
这显然会超时,因为一次展开的时间复杂度是\(O(\max(e_i)^2)\),总时间复杂度是\(O(\max(e_i)^3)\)
注意到\(k\)到\(k+1\)我们只需要把\(F(x)\)乘以\(1-x\),再除以\(1-x^2\),就可以在\(O(\max(e_i))\)的时间内更新多项式。
\(k=0\)的多项式是\(\frac{1}{(1-x)^n}\),显然可以\(O(\max(e_i))\)求
这样子就可以把总时间复杂度降低到\(O(\max(e_i)^2)\)。
最新文章
- width的数值为百分比
- Qt4.8.5在ARM9上的移植
- Linux xargs命令
- ADB安装应用报错 Segmentation fault pm install /data...
- PHP Header 缓存 --- Header 参数说明
- input两种默认显示文字方式
- [2015编程之美] 第一场C
- AngularJS Filter用法详解【转+实际测试】 格式化货币
- 2016";百度之星"; - 资格赛(Astar Round1) Problem B
- 当谈到 GitLab CI 的时候,我们该聊些什么(上篇)
- background是什么样式?
- IDEA插件和快捷设置
- Linux计划任务及压缩归档(week2_day1)--技术流ken
- 块级元素或者行内元素在设置float属性之后是否改变元素的性质?
- javascript的逼格
- 《GPU高性能编程CUDA实战》附录三 关于book.h
- oozie调度sqoop脚本时操作符号替换
- Oracle 11g 新特性 -- Oracle Restart 说明(转载)
- Curl https 访问
- 偶遇RandomAccessFile