小清新 Counting，被徐神绝杀力
直观地想我们需要求出恰好 \(m\) 轮结束的概率 \(p(m)\)，但这个显然不好直接求，我们退而求其次
用经典 trick，我们设 \(f(m)\) 表示至少点亮了 \(m\) 盏灯的概率，最后求和得到的就是带权的概率和也就是期望
考虑 \(f(m)\) 如何计算，转为计算合法局面的方案数，即在 \(n\) 个白球中选出 \(m\) 个球涂色，满足任意两个有色球之间的距离 \(\ge k\)
徐神赛时用的是捆绑法，即将一个有色球和右侧的 \(k-1\) 个无色球看成一个整体来考虑；我当时想了一个插板法的做法不过好像大差不差，最后得到的式子为：
\[f(m)=\frac{C_{n-(m-1)\times (k-1)}^{m}}{C_n^m} \]#include <bits/stdc++.h>
using llsi = long long signed int;
constexpr llsi mod = 1'000'000'007;
llsi ksm(llsi a, llsi b) {
llsi res = 1;
while(b) {
if(b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
llsi fac[100005], facinv[100005];
void init(int n = 100000) {
fac[0] = 1;
for(int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % mod;
facinv[n] = ksm(fac[n], mod - 2);
for(int i = n; i >= 1; --i) facinv[i - 1] = facinv[i] * i % mod;
return ;
}
inline llsi C(llsi a, llsi b) {
return fac[a] * facinv[b] % mod * facinv[a - b] % mod;
}
llsi f[100005];
void work() {
llsi n, k;
std::cin >> n >> k;
memset(f, 0, sizeof(llsi) * (n + 1));
f[0] = 1;
// for(llsi i = 0; i <= n; ++i) std::cerr << f[i] << char(i == n ? 10 : 32);
for(llsi m = 1; m <= n; ++m) {
llsi t = (m - 1) * (k - 1);
if(t > n || n - t < m) f[m] = 0;
else f[m] = C(n - t, m) * ksm(C(n, m), mod - 2) % mod;
}
// for(llsi i = 0; i <= n; ++i) std::cerr << f[i] << char(i == n ? 10 : 32);
llsi ans = 0;
for(llsi i = 0; i <= n; ++i)
ans += f[i];
std::cout << ans % mod << char(10);
return ;
}
int main() {
std::ios::sync_with_stdio(false);
init();
int t; std::cin >> t; while(t--) work();
return 0;
}