[AtCoder] [經典競程 90 題] 015 - Don't be too close（★6）

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_o
題目大意:
給定 $N$，對於每個 $k$ ($1 \leq k \leq N$)，回答從 $1$ 到 $N$ 中挑任意數量的數字 ($>0$)，使得挑出來的數字任意兩者絕對值差都至少 $k$ 的方法數有幾種。

---

我超爛不會做這個= =
腦袋中一直只有 $f_k(i) = f_k(i - 1) + f_k(i - k) + 1$ 的遞迴式，嘗試搞了搞也優化不下去。
解答的想法不太一樣，但也是高中基礎組合的範圍。
對於每個 $k$ ，我們每次都枚舉這次要拿多少個數字出來，因為假設 $k$ 很大的話，其實我們能拿的數字數量也有限 (實際上大概會是 $O(\frac{N}{k})$ 左右)，所以如果我們能 $O(1)$ 算給定 $k$ 且知道具體要拿幾個的時候的方法數的話，那我們就可以在 $\sum_k O(\frac{N}{k}) = O(N \log N)$ 做完這題。
給定 $k$ 且知道具體要拿幾個的時候要算方法數也很簡單，先保證每個挑出來的數字之間都至少有 $k$ 後，再把剩下的數字插回去就好，插回去的方法數其實也就是某種 H 之類的。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 100000 + 5;
constexpr int MOD = 1000000007;

constexpr int add(int a, int b) {
	return a + b >= MOD ? a + b - MOD : a + b;
}
constexpr int mul(int64_t a, int64_t b) {
	return static_cast<int>(a * b % MOD);
}
constexpr int qpow(int a, int k) {
	int r = 1;
	while (k) {
		if (k & 1) r = mul(r, a);
		a = mul(a, a); k >>= 1;
	}
	return r;
}

struct Fact {
	int tbl[N];
	constexpr Fact(): tbl() {
		tbl[0] = 1;
		for (int i = 1; i < N; ++i) {
			tbl[i] = mul(tbl[i - 1], i);
		}
	}
	constexpr int operator[](int i) const {
		return tbl[i];
	}
};
static constexpr Fact jie;

struct InvFact {
	int tbl[N];
	constexpr InvFact(): tbl() {
		int ijie = qpow(jie[N - 1], MOD - 2);
		for (int i = N - 1; i >= 0; --i) {
			tbl[i] = ijie;
			ijie = mul(ijie, i);
		}
	}
	constexpr int operator[](int i) const {
		return tbl[i];
	}
};
static constexpr InvFact inv_jie;

constexpr int C(int i, int j) {
	return mul(jie[i], mul(inv_jie[j], inv_jie[i - j]));
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n; cin >> n;
	for (int k = 1; k <= n; ++k) {
		int ans = 0;
		for (int i = 1; i <= n; ++i) {
			int used = (i - 1) * k + 1;
			if (used > n) break;
			int lef = n - used;
			ans = add(ans, C(lef + i, i));
		}
		cout << ans << '\n';
	}
	return 0;
}