考虑把式子化简:
i=0∑n(in)ik=i=1∑n(in)j=1∑k{kj}(i−j)!i!
考虑把阶乘处理掉,因为太丑了:
i=0∑n(in)ik=j=1∑k{kj}j!i=0∑n(in)(ji)
把组合数结合一下然后化简:
i=0∑n(in)ik=j=1∑k{kj}j!i=0∑n(jn)(n−jn−i)
把 i=0∑n(n−jn−i) 看作 (jn) 的系数,然后将 i 整体修改得到:
i=0∑n(in)ik=j=1∑k{kj}j!(jn)i=0∑n−j(in−i)
最后根据组合数的性质,化简出:
i=0∑n(in)ik=j=1∑k{kj}j!(jn)2n−j
虽然是垃圾的 O(klogn),但是你就说能不能过吧。