LOJ3120 CTS2019 珍珠 生成函数、二项式反演、NTT
题目大意:给出一个长度为\(n\)的序列\(a_i\),序列中每一个数可以取\(1\)到\(D\)中的所有数。问共有多少个序列满足:设\(p_i\)表示第\(i\)个数在序列中出现的次数,\(\sum\limits_{i=1}^D \lfloor \frac{p_i}{2} \rfloor \geq m\)。\(D \leq 10^5 , 0 \leq m \leq n \leq 10^9\)
在有生之年切掉laofu的多项式题,全场唯一一个写多项式求逆的,其他人都直接卷积,然后发现自己的做法其实并不需要多项式求逆……
首先上面的条件等价于:\(\sum\limits_{i=1}^D [2 \not\mid p_i] \leq n - 2m\)。那么一种想法是求出强制其中\(n - 2m + 1\)个数字出现次数为奇数,其他的数出现次数为偶数。那么这样的方案数是\(\binom{D}{n - 2m + 1} [x^n](\frac{e^x - e^{-x}}{2})^{n - 2m + 1} (\frac{e^x + e^{-x}}{2})^{D - (n - 2m + 1)}\),非常难算。不妨考虑容斥计算。
先做几个特判:\(n < 2m\)时答案为\(0\);\(D < n - 2m + 1\)时答案为\(D^n\)。
不妨设\(f_i\)表示强制其中\(i\)个数字出现次数为奇数,其他的数出现次数随意的方案数,那么\(f_i = \binom{D}{i} [x^n](\frac{e^x - e^{-x}}{2})^{i} e^{(D - i)x}\),经过化简可以得到\(f_i = i! \binom{D}{i} \frac{1}{2^i} \sum\limits_{j=0}^i \frac{(-1)^j (D - 2j)^n}{(i-j)!j!}\)。不难发现后面是一个卷积形式,使用\(NTT\)在\(O(DlogD)\)的时间复杂度内可以求出所有的\(f_i\)。
然后又设\(g_i\)表示恰好\(i\)个数字出现奇数次的方案数,就和HAOI2018 染色一样用NTT加速二项式反演即可。
最后答案就是\(\sum\limits_{i=0}^{n - 2m} g_i\)。
最新文章
- 使用js批量选中功能实现更改数据库中的status状态值(批量展示)
- vs版本转换工具
- 类中用const限定的成员函数
- Aidl的使用步骤
- 关于iscroll阻止浏览器默认动作
- HDU3466背包01
- ubuntu下解压zip文件乱码
- 《Python 学习手册4th》 第十二章 if测试和语法规则
- Memcached快递上手之C#
- .net—— webservice的新建、发布、使用(最全、最简单)【原创】
- 在Debian9(linux)上使用 的 python 3 IDLE(已经安装了python 2.7 的情况下)
- 什么?云数据库也能C位出道?
- luogu P2617 Dynamic Rankings &;&; bzoj 1901 (带修改区间第k大)
- 使用 VSTS 进行 CI 的过程中,无法识别 .NET Core 2.x 的情况处理
- LeetCode 953 Verifying an Alien Dictionary 解题报告
- Python3基础 list extend 合并列表
- 解决libc.so.6: version `GLIBC_2.14&;#39; not found问题
- HDU1024(DP)
- java.lang.AbstractStringBuilder.enlargeBuffer
- DB分布式 跨库分页
热门文章
- BZOJ 1213: [HNOI2004]高精度开根
- 第03组 Alpha冲刺(1/4)
- 58、Spark Streaming: DStream的output操作以及foreachRDD详解
- queue怎么用咧↓↓↓
- 腾讯云手动搭建nginx+php-fpm并自启动
- Ubuntu 16.04与Win10双系统双硬盘安装图解
- css3实现水平垂直居中------(特别注意,里边的固定还是不固定)
- java中JSON转含泛型对象
- springcloud添加自定义的endpoint来实现平滑发布
- Git push origin dev-rgq-istokenstatus 【dev-rgq-istokenstatus ->; dev-rgq-istokenstatus】