1 条题解
-
0Takagi-san (njnu19200437) LV 10 MOD @ 2021-11-21 17:27:40
#include <iostream> #include <vector> typedef long long ll; using namespace std; const int mod = 1000000007; ll n, k; int main() { cin >> n >> k; vector<bool> primes(1e6 + 10, true); vector<int> primess; for (int i = 2; i * i < primes.size(); ++i) { if (primes[i]) { int j = 2 * i; while (j < primes.size()) { primes[j] = false; j += i; } } } // Get all primes. for (int i = 2; i < primes.size(); ++i) { if (primes[i]) { primess.push_back(i); } } vector<int> small = vector<int>(k + 1, 0); for (int i = 0; i < small.size(); ++i) small[i] = i + 1; vector<ll> big = vector<ll>(k + 1, 0); for (int i = 0; i < big.size(); ++i) big[i] = n - k + 1 + i; ll ans = 1; for (auto p : primess) { // consider small int tmp = 0; for (int i = p - 1; i < k; i += p) { while (small[i] % p == 0) { --tmp; small[i] /= p; } } // consider big for (int i = ((n - k + 1) / p * p) - (n - k + 1); i < k; i += p) { if (i < 0) continue; while (big[i] % p == 0) { ++tmp; big[i] /= p; } } ans = ans * (tmp + 1) % mod; } for (int i = 0; i < k; ++i) { if (big[i] > 1) { ans = ans * 2 % mod; } } cout << ans << endl; return 0; }
- 1
信息
- ID
- 1303
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 97
- 已通过
- 4
- 通过率
- 4%
- 被复制
- 1
- 上传者