A
根号分治。
对于 (kle sqrt{n}) 的情况，预处理 (f_{i,j}) 表示长为 (i) 的棋盘，黑点之间相差 (ge k) 的方案数，那么 (f_{i,j}=f_{i-1,j}+f_{i-j,j})。
对于 (k>sqrt{n}) 的情况，考虑组合数：(dbinom{n-1-kx+k+x}{x}) 即为在长为 (n) 的棋盘上选 (x) 个地方染成黑点，且黑点之间距离 (ge k) 的方案数。
考虑有“在位置 (p) 上强制染成白色”这个限制怎么做：可以让 (p) 染成黑色，那么 ([max{1,p-k},p-1],[p+1,min{n,p+k}]) 这两个区间内都不能染黑。对于可以染色的前缀和后缀算一下即可。
时间复杂度 (O(msqrt{n}))。