CF932E solution
NaCly_Fish
2020-05-01 20:21:30
~~嗯,你看这群人,才推出 $\Theta(k \log k)$ 就不往下了,真是太逊了~~
提供一种时间复杂度 $\Theta(k)$ 的做法。
$$\sum_{i=0}^n \binom ni i^k$$
将 $i^k$ 用第二类 Stirling 数展开
$$=\sum_{i=0}^n \binom ni \sum_{j=1}^k \begin{Bmatrix} k \\ j \end{Bmatrix}i^{\underline j}$$
$$=\sum_{j=1}^k \begin{Bmatrix} k \\ j \end{Bmatrix}j! \sum_{i=0}^n \binom ni \binom ij$$
$$=\sum_{j=1}^k \begin{Bmatrix} k \\ j \end{Bmatrix}j! \sum_{i=0}^n \binom nj \binom{n-j}{i-j}$$
$$=\sum_{j=1}^k \begin{Bmatrix} k \\ j \end{Bmatrix}j! \binom nj \sum_{i=0}^{n-j} \binom{n-j}{i}$$
$$=\sum_{j=1}^k \begin{Bmatrix} k \\ j \end{Bmatrix} j! \binom{n}{j} 2^{n-j}$$
很多人推到这里就停了,因为一行第二类 Stirling 数可以很容易的用一次卷积计算;但将其进一步展开,就可以做到更优的复杂度。
在 $n > k$ 的时候,原式等于
$$\sum_{j=1}^k \binom nj 2^{n-j} \sum_{i=1}^j \binom jii^k(-1)^{j-i}$$
~~使用魔法~~ 交换一下求和顺序
$$=\sum_{i=1}^k i^k\sum_{j=i}^k \binom nj\binom ji 2^{n-j}(-1)^{j-i}$$
$$=\sum_{i=1}^k i^k\binom ni \sum_{j=i}^k \binom{n-i}{j-i}2^{n-j}(-1)^{j-i}$$
$$=\sum_{i=1}^k \binom ni i^k 2^{n-i}\sum_{j=0}^{k-i} \binom{n-i}{j} \left( - \frac 12\right)^j$$
设 $f_i$ 为后面那个和式的值,考虑递推:
(为了方便下面表示,设 $w=-0.5$)
$$f_{i}-f_{i+1}$$
$$= \left(\sum_{j=0}^{k-i} \binom{n-i}{j} w^j \right)-\left( \sum_{j=0}^{k-i-1} \binom{n-i-1}{j}w^j\right)$$
把前一个和式中 $j=k-i$ 的项提出来,其他的并进去
$$= \binom{n-i}{k-i}w^{k-i}+ \sum_{j=0}^{k-i-1} \left( \binom{n-i}{j} - \binom{n-i-1}{j}\right) w^j$$
$$=\binom{n-i}{k-i}w^{k-i}+\sum_{j=0}^{k-i-1} \binom{n-i-1}{j-1} w^j$$
$$= \binom{n-i}{k-i}w^{k-i}+w\sum_{j=0}^{k-i-2} \binom{n-i-1}{j}w^j$$
再把那个和式最后缺的一项补回来
$$=\binom{n-i}{k-i} w^{k-i}+w \left( f_{i+1}-\binom{n-i-1}{k-i-1}w^{k-i-1}\right)$$
$$=\binom{n-i}{k-i} w^{k-i}+wf_{i+1}-\binom{n-i-1}{k-i-1}w^{k-i}$$
$$= \binom{n-i-1}{k-i}w^{k-i}+wf_{i+1}$$
于是得到递推式
$$f_i=(w+1)f_{i+1} + \binom{n-i-1}{k-i}w^{k-i}$$
递推处理组合数,再线性筛出 $i^k$,就可以做到严格的 $\Theta(k)$ 了。
```cpp
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize (2)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 5007
#define ll long long
#define p 1000000007
#define reg register
using namespace std;
inline int power(int a,int t){
int res = 1;
while(t){
if(t&1) res = (ll)res*a%p;
a = (ll)a*a%p;
t >>= 1;
}
return res;
}
int n,m,k,cnt;
int f[N],inv[N],pw[N],pr[N>>1],c[N];
int solve1(){
int res = 0;
for(reg int i=1;i<=n;++i) res = (res+(ll)c[i]*pw[i])%p;
return res;
}
const int w = 500000003;
int solve2(){
int c2,mul,res = 0;
mul = c2 = f[k] = 1;
for(reg int i=k-1;i;--i){
c2 = (ll)c2*(n-i-1)%p*inv[k-i]%p;
mul = (ll)mul*w%p;
f[i] = ((ll)c2*mul+(ll)(w+1)*f[i+1])%p;
}
mul = p-w;
for(reg int i=1;i<=k;++i){
res = (res+(ll)pw[i]*c[i]%p*mul%p*f[i])%p;
mul = (ll)mul*(p-w)%p;
}
res = (ll)res*power(2,n)%p;
return res;
}
int main(){
scanf("%d%d%d",&n,&k);
c[0] = inv[1] = pw[1] = 1;
c[1] = n;
for(reg int i=2;i<=k+1;++i){
inv[i] = (ll)(p-p/i)*inv[p%i]%p;
c[i] = (ll)c[i-1]*inv[i]%p*(n-i+1)%p;
if(!pw[i]){
pr[++cnt] = i;
pw[i] = power(i,k);
}
for(reg int j=1;j<=cnt&&i*pr[j]<=k;++j){
pw[i*pr[j]] = (ll)pw[i]*pw[pr[j]]%p;
if(i%pr[j]==0) break;
}
}
if(n<=k+1) printf("%d",solve1());
else printf("%d",solve2());
return 0;
}
```
~~CF1278F 和这题其实是一个做法,双倍经验~~