QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#374633 | #8339. Rooted Tree | ucup-team228# | TL | 272ms | 84920kb | C++20 | 2.6kb | 2024-04-02 16:01:08 | 2024-04-02 16:01:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string to_string(string a) { return '"' + a + '"'; }
string to_string(char a) { return "'" + string(1, a) + "'"; }
string to_string(const char* a) { return to_string((string) a); }
string to_string(bool a) { return a ? "true" : "false"; }
template <class T1, class T2>
string to_string(pair<T1, T2> a) {
return "(" + to_string(a.first) + ", " + to_string(a.second) + ")";
}
template <class T>
string to_string(T a) {
bool first = true; string res = "{";
for (const auto& i : a) {
if (!first) res += ", ";
first = false;
res += to_string(i);
}
res += "}";
return res;
}
void debug_out() { cerr << endl; }
template <class T1, class... T2>
void debug_out(T1 a, T2... b) {
cerr << " " << to_string(a);
debug_out(b...);
}
#ifdef LOCAL
#define out(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define out(...) 42
#endif
const int mod = 1e9 + 9;
int add(int a, int b) {
return a + b >= mod ? a + b - mod : a + b;
}
int sub(int a, int b) {
return a - b < 0 ? a - b + mod : a - b;
}
int mult(int a, int b) {
return int(1ll * a * b % mod);
}
int binpow(int a, int n) {
int res = 1;
for (; n >= 1; n >>= 1) {
if (n & 1) res = mult(res, a);
a = mult(a, a);
}
return res;
}
int inv(int a) {
return binpow(a, mod - 2);
}
#define div my_div
int div(int a, int b) {
return mult(a, inv(b));
}
const int N = 1e7 + 10;
int f[N];
int fact[N], inv_fact[N];
void init() {
fact[0] = 1;
for (int i = 1; i <= N - 1; i++) {
fact[i] = mult(fact[i - 1], i);
}
inv_fact[N - 1] = inv(fact[N - 1]);
for (int i = N - 2; i >= 0; i--) {
inv_fact[i] = mult(inv_fact[i + 1], i + 1);
}
}
int C(int n, int k) {
if (n < 0 || k < 0 || n < k) {
return 0;
} else {
return mult(fact[n], mult(inv_fact[k], inv_fact[n - k]));
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
init();
int m, k;
cin >> m >> k;
f[0] = 0;
int ans = 0;
for (int i = 1; i <= k; i++) {
ans = add(ans, mult(add(f[i - 1], 1), m)); // (f[i - 1] + 1) * m
int tot = 1 + mult(i, m - 1);
f[i] = add(mult(div(m, tot), add(f[i - 1], 1)), mult(div(sub(tot, m), tot), f[i - 1]));
}
cout << ans << "\n";
#ifdef LOCAL
cout << "\nTime elapsed: " << double(clock()) / CLOCKS_PER_SEC << " s.\n";
#endif
}
详细
Test #1:
score: 100
Accepted
time: 102ms
memory: 81840kb
input:
6 2
output:
18
result:
ok 1 number(s): "18"
Test #2:
score: 0
Accepted
time: 87ms
memory: 82268kb
input:
2 6
output:
600000038
result:
ok 1 number(s): "600000038"
Test #3:
score: 0
Accepted
time: 272ms
memory: 84920kb
input:
83 613210
output:
424200026
result:
ok 1 number(s): "424200026"
Test #4:
score: -100
Time Limit Exceeded
input:
48 6713156