[BZOJ4555 TJOI2016 HEOI2016 求和]
第一篇博客,请大家多多关照。(鞠躬
BZOJ4555 TJOI2016 HEOI2016 求和
题意:
给定一个正整数\(n\)(\(1\leqq n \leqq100000\)),求:
\[
\begin{align*}
f(n)=\sum_{i=0}^n\sum_{j=0}^i \begin{Bmatrix}i\\j\end{Bmatrix}\times2^j\times(j!)
\end{align*}
\]
题解:
第二类斯特林数公式题,题目中很良心地给了我们第二类斯特林数的递推公式:
\[
\begin{align*}
\begin{Bmatrix}i\\j\end{Bmatrix}=j\times \begin{Bmatrix}i-1\\j\end{Bmatrix}+\begin{Bmatrix}i-1\\j-1\end{Bmatrix}
\end{align*},1\leqq j\leqq i-1\\
\begin{Bmatrix}i\\i\end{Bmatrix}=[i\geqq0]
\]
于是我们愉快地用上面的公式,于是我们愉快地T掉。
所以,我们应该考虑有没有一种能让我们在\(O(logn)\)内求出我们需要的每一项第二类斯特林数的方法。
有,我们可以用容斥定理求出斯特林数的通项公式(我并不会,是背的):
\[
\begin{align*}
\begin{Bmatrix}n\\m\end{Bmatrix}&=\frac{1}{m!}\sum_{k=0}^m\dbinom{m}{k}(m-k)^n(-1)^k\\
&=\frac{1}{m!}\sum_{k=0}^m\frac{m!}{k!(m-k)!}(m-k)^n(-1)^k\\
&=\sum_{k=0}^m\frac{1}{k!}\frac{(m-k)^n}{(m-k)!}(-1)^k
\end{align*}
\]
带入原式中:
\[
\begin{align*}
f(n)&=\sum_{i=0}^n\sum_{j=0}^i \begin{Bmatrix}i\\j\end{Bmatrix}\times2^j\times(j!)\\
\because当j>i时,\begin{Bmatrix}i\\j\end{Bmatrix}=0\\&=\sum_{j=0}^n2^j\times(j!)\sum_{i=0}^n\sum_{k=0}^j\frac{(-1)^k}{k!}\frac{(j-k)^i}{(j-k)!}\\
&=\sum_{j=0}^n2^j\times(j!)\sum_{k=0}^j\frac{(-1)^k}{k!}\sum_{i=0}^n\frac{(j-k)^i}{(j-k)!}
\end{align*}
\]
出现了卷积形式,记\(A(x)=\sum_{k=0}^x\frac{1}{k!}\),\(B(x)=\sum_{i=0}^n\frac{x^i}{x!}\)
预处理\(2^j\)、\(j!\),用ntt处理\(\sum_{j=0}^n\sum_{i+k=j}A(i)\times B(k)\)
时间复杂度:\(O(nlogn)\)
最新文章
- js学习篇--数组按升序降序排列
- ecshop 点击领取红包
- 【转载】CSS 盒子模型
- log4j:WARN Please initialize the log4j system properly.解决
- Windows 10正式版官方原版ISO镜像下载
- Bestcoder Round#45
- Android Studio 100 tips and tricks
- 探测器 C++ Singleton(辛格尔顿)
- AOJ2249最短路+最小费用
- 201521123090 《Java程序设计》第5周学习总结
- SpringMVC的流程分析(一)—— 整体流程概括
- MySQL笔记-union
- androd输入管理系统机制解析
- 用redis的scan命令代替keys命令,以及在spring-data-redis中遇到的问题
- Intersection(Check)
- Python 爬虫入门(一)
- Oracle居然把Java EE的未来押在Rest API上了
- FastDFS简介和安装
- 帝国CMS网站迁移方法
- Tomcat类加载机制触发的Too many open files问题分析(转)
热门文章
- 设置cookie的方法
- [NOIP2009提高组]靶形数独
- 【UVa 12563】Jin Ge Jin Qu hao
- ECNUOJ 2856 仰望星空
- error C2440: “static_cast”: 无法从“LRESULT (__thiscall CTextProgressCtrl::* )(UINT,LPCTSTR)”转换为“LRESULT (__thiscall CWnd::* )(WPARAM,LPARAM)
- 协变 &; 逆变
- 跨域post 及 使用token防止csrf 攻击
- 杭电1425 sort
- legend---七、jquery如何选中select的selected的选择上的自定义属性
- Redis封装之Set