SP2742题解
2024-10-16 01:19:01
晚自习用10min推出结论,太屑了
设 \(S=\sum_{i=1}^n a_i\),很显然每个位置的答案 \(ans_i\) 只和 \(a_i\) 和 \(S\) 有关。让我们打个表,找一下规律:
\[a_i
\]
\]
\[S-a_i
\]
\]
\[nS-2S+a_i
\]
\]
\[n^2S-3nS+3S-a_i
\]
\]
\[n^3S-4n^2S+6nS-4S+a_i
\]
\]
我们发现系数是杨辉三角,也就是二项式系数。
所以答案是:
\[\sum_{i=0}^{T-1}\binom T i(-1)^in^{T-i-1}S+(-1)^Ta_i
\]
\]
二项式定理化简一下,答案就是 \(\frac {(n-1)^T+(-1)^{T+1}} n \times S+(-1)^Ta_i\)。
有没有什么严格的证明?
这里需要用到生成函数。
设 \(f_{T,i}\) 是变换 \(T\) 次后,\(n^{i-1}S\) 的系数。
很明显有 \(f_{T,i}=nf_{T-1,i-1}-f_{T-1,i}\)。
设 \(F_T(x)=\sum_{i=0}^T f_{T,i}x^i\),我们要求的就是 \(\frac {F_T(n)-f_{T,0}} n \times S+f_{T,0}a_i\)。
考虑 \(F_T(x)\) 与 \(F_{T-1}(x)\) 的关系,如果将上面的递推式中的 \(n\) 看做 \(x\),很明显有 \(F_T(x)=(x-1)F_{T-1}(x)\)。
而我们又知道 \(F_0(x)=1\),所以 \(F_T(x)=(x-1)^T\)。
最新文章
- IOS第四天-新浪微博 -存储优化OAuth授权账号信息,下拉刷新,字典转模型
- Bzoj2683 简单题 [CDQ分治]
- pc, 手机全屏
- SQL查询数据库是否存在
- Spring 使用注解方式进行事务管理
- Eclipse小技巧<;一>;
- Implementing Remote Validation in MVC
- DAC,MAC和SELinux,SEAndroid
- 015_xml_函数
- socket用法以及tomcat静态动态页面的加载
- ALOS卫星介绍
- 作为Qt 合作伙伴的V-Play,比大家都领先了一步 planet.qt.io
- c#设计模式-单例模式(面试题)
- CSS3的颜色渐变效果
- UVA-10954 贪心+优先队列
- 数据库中row_number()、rank()、dense_rank() 的区别
- javascript项目实战---ajax实现无刷新分页
- modbus tcp 入门详解
- HDU 5884 Sort(二分+优先队列)
- Linux vm运行参数 - OOM相关的参数
热门文章
- 打印流(printStream)
- TCP的报文详细解读
- LeetCode随缘刷题之转化成小写字母
- haproxy https实现
- [题解]Mail.Ru Cup 2018 Round 1 - B. Appending Mex
- [题解]UVA10129 Play on Words
- 数据分析六个步骤,一款BI工具即可全部搞定
- 图表制作软件哪家强?当属火爆商业智能圈的Smartbi
- IDisposable?释放非托管资源接口
- Map<;String,String>;转Json转Base64