[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 之類的。
題目大意:
給定 $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;
}
留言
張貼留言