[ans=sumlimits_{i=1}^{n}dbinom{n}{i}
]
我们有
[n^m=sumlimits_{i=0}^{m}egin{Bmatrix}m\iend{Bmatrix}i!dbinom{n}{i}
]
得到
[=sumlimits_{i=1}^{n}dbinom{n}{i}sumlimits_{j=0}^{k}egin{Bmatrix}k\jend{Bmatrix}j!dbinom{i}{j}
]
[=sumlimits_{j=0}^{k}egin{Bmatrix}k\jend{Bmatrix}j!sumlimits_{i=1}^{n}dbinom{n}{i}dbinom{i}{j}
]
[=sumlimits_{j=0}^{k}egin{Bmatrix}k\jend{Bmatrix}j!sumlimits_{i=1}^{n}dbinom{n}{j}dbinom{n-j}{i-j}
]
[=sumlimits_{j=0}^{k}egin{Bmatrix}k\jend{Bmatrix}j!dbinom{n}{j}sumlimits_{i=1}^{n}dbinom{n-j}{i-j}
]
[=sumlimits_{j=0}^{k}egin{Bmatrix}k\jend{Bmatrix}j!dbinom{n}{j}2^{n-j}
]
此时可以做到(O(klogk))
用通项公式展开(egin{Bmatrix}k\jend{Bmatrix})得到
[=sumlimits_{j=0}^{k}dbinom{n}{j}2^{n-j}sumlimits_{i=1}^{j}(-1)^idbinom{j}{i}(j-i)^k
]
令第二个求和的(i)变为(j-i)
[=sumlimits_{j=0}^{k}dbinom{n}{j}2^{n-j}sumlimits_{i=1}^{j}(-1)^{j-i}dbinom{j}{i}i^k
]
[=sumlimits_{i=1}^{k}i^ksumlimits_{j=i}^{k}dbinom{n}{j}dbinom{j}{i}2^{n-j}(-1)^{j-i}
]
[=sumlimits_{i=1}^{k}i^ksumlimits_{j=i}^{k}dbinom{n}{i}dbinom{n-i}{j-i}2^{n-j}(-1)^{j-i}
]
[=sumlimits_{i=1}^{k}i^kdbinom{n}{i}sumlimits_{j=i}^{k}dbinom{n-i}{j-i}2^{n-j}(-1)^{j-i}
]
[=sumlimits_{i=1}^{k}i^kdbinom{n}{i}2^{n-i}sumlimits_{j=i}^{k}dbinom{n-i}{j-i}(-frac{1}{2})^{j}
]
设(w=-0.5,f_i)为后面的和式
容易得到(f_k=1)，考虑递推
[f_i-f_{i+1}
]
[=(sumlimits_{j=0}^{k-i}dbinom{n-i}{j}w^j)-(sumlimits_{j=0}^{k-i-1}dbinom{n-i-1}{j}w^j)
]
把第一个和式中的(k-i)项提出来，其他的并入第二项
[=dbinom{n-i}{k-i}w^{k-i}+sumlimits_{j=0}^{k-i-1}(dbinom{n-i}{j}-dbinom{n-i-1}{j})w^j
]
[=dbinom{n-i}{k-i}w^{k-i}+sumlimits_{j=0}^{k-i-1}(dbinom{n-i-1}{j-1})w^j
]
令(j=j-1)
[=dbinom{n-i}{k-i}w^{k-i}+wsumlimits_{j=0}^{k-i-2}(dbinom{n-i-1}{j-1})w^j
]
[=dbinom{n-i}{k-i}w^{k-i}+w(f_{i+1}-dbinom{n-i-1}{k-i-1}w^{k-i-1})
]
[=dbinom{n-i}{k-i}w^{k-i}+wf_{i+1}-dbinom{n-i-1}{k-i-1}w^{k-i}
]
[=dbinom{n-i-1}{k-i}w^{k-i}+wf_{i+1}
]
得到
[f_i=(w+1)f_i+dbinom{n-i-1}{k-i}w^{k-i}
]
所以
[ans=sumlimits_{i=1}^{k}dbinom{n}{i}i^k2^{n-i}f_i
]
(f_i)可以(O(k))递推了，(i^k)是积性函数可以线性筛