Super Particle Cannon
Description
求
k∑i=0Cinmod2333
Solution
设
f(n,k)=k∑i=0Cin即
k∑i=0Ci/pn/p×Ci%pn%p数论分块一下,此处将其分成 k/p 个块,许多数字同属一个块,就一起算掉。
p−1∑i=0Cin%pC0n/p+p−1∑i=0Cin%pC1n/p+…+p−1∑i=0Cin%pCk/p−1n/p+k%p∑i=0Cin%pCk/pn/p把 ∑p−1i=0Cin%p 提出来
p−1∑i=0Cin%pk∑i=0Ci/p−1n/p也就是
f(n%p,p−1)×f(n/p,k/p−1)最后一个不完整的块单独处理
k%p∑i=0Cin%p即
f(n%p,k%p)所以
f(n,k)=f(n%p,p−1)×f(n/p,k/p−1)+Ck/pn/p×f(n%p,k%p)预处理组合数,套个 Lucas 就完了。
Code:
1 |
|