【题解】CTS2019珍珠(二项式反演+卷积)
【题解】CTS2019珍珠
题目就是要满足这样一个条件\(c_i\)代表出现次数
\[
\sum {[\dfrac {c_i } 2]} \ge 2m
\]
显然\(\sum c_i=n\)所以,而且假如\(c_i\)是\(2\)的约数就有正常的贡献,如果不是就有少一点的贡献,那么
\[
\sum^D_{i=1} {[2\mid c_i]} > n-2m
\]
设\(f_i\)为钦定有\(i\)种颜色出现偶数次的方案。问题瞬间就变成了HAOI染色...
则有
\[
f_i={D\choose i}[x^n]n!(\dfrac {e^x+e ^{-x}}{2})^i{(e^x)}^{D-i}
\]
选出钦定的\(i\)个颜色,后面是序列的生成方式。
\[
2^if_i={D\choose i}[x^n]n!( {e^x+e ^{-x}})^i{(e^x)}^{D-i}
\]
展开\(^i\)
\[
2^if_i={D\choose i}[x^n]n!\sum_{j=0}^i{i\choose j}{(e^x)}^{D+2j-2i}
\]
由于是求\([x^n]\)所以
\[
2^if_i={D\choose i}n!\sum_{j=0}^i{i\choose j}\dfrac {{(D+2j-2i)}^n}{n!}
\]
\[
={D\choose i}\sum_{j=0}^i{i\choose j} {{(D+2j-2i)}^n}
\]
所以
\[
\dfrac {2^if_i}{{D\choose i}i!}=\sum_{j=0}^i \dfrac {(-(2i-2j-D))^n}{j!(i-j)!}
\]
右边的式子直接NTT得到。
然而我们知道,这样的钦定是有重复的,具体如何重复参考[【题解】HAOI2018]染色(NTT+容斥/二项式反演)。我们直接二项式反演:
设\(g_i\)表示恰好\(i\)种颜色出现次数为偶数的方案,则考虑一下\(g_j\)在\(f_i\)出现的次数
\[
f_i=\sum_{j=i}^D {j\choose i}g_i
\]
直接二项式反演
\[
g_i=\sum_{j=i}^D (-1)^{j-i}{j\choose i}f_j
\]
下标从0没问题,变一下:
\[
g_i=\sum_{j=0}^D (-1)^{j-i}\dfrac {j!}{i!(j-i)!}f_j
\]
整理
\[
\dfrac {g_i}{i!}=\sum_{j=0}^D \dfrac{(-1)^{j-i}\times j!f_j}{(j-i)!}
\]
reverse一下,右边又直接NTT
最终答案:
\[
\sum_{i=n-2m+1}^D g_i
\]
你觉得肯定做不了,\(n\le 1e9\)啊,但是考虑一些边界情况:
- \(n <2m\)答案为0
- \(n-2m+1>D\)答案为\(D^n\)
所以如果用多项式算法的条件是
\[
n\ge2m\\n-2m+1\le D=1e5\\
\]
多项式的maxn开\(1<<18\)就行了。
代码真的懒得写就是套套板子调调参。
最新文章
- oracle的特殊权限s bit丢失
- 把 SQL Server 迁移到 Linux?不如换成 MySQL
- 关于如何在Android、Java等非微软平台上建立高信任的SharePoint应用程序
- php日常日志写入格式记录
- java byte&;0xFF
- viso2010从mysql中导出ER图
- jQuery ui autocomplete下拉列表样式失效解决,三种获取数据源方式,
- AFNetWorking 队列请求
- Asp.Net(C#)自动执行计划任务的程序实例分析
- ios开发跳转
- Codeforces Round #343 (Div. 2) B. Far Relative’s Problem
- javascript——基本包装类型
- (5)Python字典
- 初步了解HTML
- WebLogic 11g的安装与配置详谈配置详谈
- 16mysql1
- jquery 中prop和 attr
- LeetCode-97.交错字符串
- Notification的功能和用法 加薪通知
- [转]vim 退格键(backspace)不能用