正睿2019省选附加赛 Day10 (这篇其实已经都咕咕了...)
2024-10-19 23:08:15
2019.3.13
A.算算算(二项式定理 斯特林数)
\(x^k\)可以用二项式定理展开，需要维护的就是\(0\sim k\)次方的\(\sum_{j}F(j,i)\)。加入一个数时，每一项都要再用一遍二项式定理更新，复杂度是\(O(nk^2)\)的。
每次加入的数都是一位数，考虑如何从\(x^k\)变到\((x+1)^k\)。注意到有\(x^k=\sum\limits_{i=0}^kS(k,i)C(x,i)i!\)（\(S\)是第二类斯特林数），从\(x\)变成\(x+1\)只需维护\(C(x+1,i)\)即可（然后可以用这个式子\(O(k)\)算出\((x+1)^k\)）。
\(C(x+1,i)=C(x,i)+C(x,i-1)\)，所以这个可以\(O(1)\)更新。
\(x^k\)变成\((x+a)^k\)就重复这个过程\(a\)次即可。
\(a^k+b^k=\sum\limits_{i=0}^kS(k,i)\big(C(a,i)+C(b,i)\big)i!\)，新加入一个数可以直接更新\(C(x,i)\)。
复杂度\(O(Ank)\)，\(A\)是所有数位的平均值，随机数据下是\(4.5\)。
还有一种容斥做法，\(O(nk)\)的，太菜了看不懂。
\[s_i=\sum_{j=1}^ia_j\\Ans_i=\sum_{j=0}^k(-1)^jC_k^js_i^{k-j}\left(\sum_{l=0}^{i-1}s_l^j\right)
\]
\]
咕咕了
B.买买买
看不懂。留坑。（然而高考前怕是填不上了...）
C.树树树
貌似是模板题，不管了。
最新文章
- 记一次WinForm中屏蔽空格键对按钮的作用
- Objective-C精选字符串处理方法
- parseInt 和parseFloat 区别
- 使用jailkit chroot更改ssh用户根目录
- jQuery版本升级踩坑大全
- iOS开发——实用篇Swift篇&QQ登入界面实现
- Oracle数据库间的数据复制 - SQLPlus中的COPY命令
- vmware workstation 10.0.1 install mac os mavericks
- hadoop集群之HDFS和YARN启动和停止命令
- Nginx 之一：编译安装nginx 1.8.1 及配置
- POJ 3667 splay区间盘整运动
- udp接收
- SQL语句创建access表
- Eclipse打jar包，资源文件的读取
- SAI窗口无法移动
- 自定义线程池reject策略
- java 按字节读写二进制文件（Base64编码解码）
- DBSCAN密度聚类
- Spring Boot 揭秘与实战（二） 数据存储篇 - ElasticSearch
- js数据类型和变量