BZOJ4555求和(cdq分治+NTT)
2024-08-30 17:00:39
题意:
输出f(n)对998244353(7 × 17 × 223 + 1)取模的结果。1 ≤ n ≤ 100000
其中S(i,j)是第二类Stirling数,即有i个球,丢到j个盒子中,要求盒子不为空的方案总数
S(i,j)=S(i-1,j-1)+j*S(i-1,j) (前面一项表示第i个球单独放到一个盒子中,后面一项表示放到前面j个盒子中的某一个)
分析:
首先这个n不是丧心病狂的大,所以感觉可以求i=1时的结果,i=2时的结果,i=3时的结果……,于是可以不看第一个Σ
我们考虑后面的这项
这个表示有n个球,要丢到i个盒子中,这些盒子是有序的,并且球在盒子中有两种状态
换个方式枚举,枚举最后一个盒子中球的个数,那么有
右边这个有卷积的感觉了,再来弄一下,将组合公式带进去
令G(n)=g(n)/n!
那么有
这个inv(n-i)表示模意义下(n-i)!的逆元,这个预处理很简单
问题是这个并不是很简单的卷积,因为卷积是A(n)=ΣB(i)*C(n-i),但这里A=C
这里可以采取cdq分治的思想
我们要求G(l..r)
第一步:求G(l..mid)
第二步:求G(l..mid)对G(mid+1,r)的影响
第三步:求G(mid+1,r)
具体说下第二步
这时候G(l,mid)都已经确定了,它们对G(mid+1)的贡献是容易发现就是G(0,mid-l)和inv(0,r-l)的卷积
所以就是cdq分治过程中进行FFT
但因为这题数字很大,所以用FFT会出现精度上的问题
而且这题模数那么特殊,所以直接上NTT……
T(n)=T(n/2)+O(nlogn)
这个复杂度应该介于O(nlogn)和O(nlog^2n)之间吧……
最新文章
- jQuery2.x源码解析(缓存篇)
- Stream 和 byte[]
- C语言判断文件是否存在(转)
- IOS文字属性备注
- 验证身份证合法性的js
- C#用DesignSurface实现一个简单的窗体设计器
- 关于SpringMVC中text/plain的编码导致的乱码问题解决方法
- hdu 5700区间交(线段树)
- 4455[Zjoi2016]小星星 容斥+dp
- CSS实现动画特效导航栏
- centos 7 修改系统屏幕分辨率
- Python函数绘图
- 修改tomcat启动窗口的名称
- ES6 声明变量的6种方法
- 旋转数组的最小数字(python)
- 【AtCoder】AGC029(A-E)
- 机器学习集成算法--- 朴素贝叶斯,k-近邻算法,决策树,支持向量机(SVM),Logistic回归
- AFNetWorking能做什么
- 利用Py-Socket模块做的一个不登陆windows服务器自动实现替换或者调用自动拨号功能
- 机器学习之路: 初识tensorflow 第一个程序