QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#762680 | #8023. The Journey of Geor Autumn | FAKUMARER | WA | 1ms | 7820kb | C++23 | 1021b | 2024-11-19 16:08:40 | 2024-11-19 16:08:47 |
Judging History
answer
# include <bits/stdc++.h>
const int32_t maxn = 10000005;
const int32_t mod = 998244353;
int32_t n, k;
int32_t f[maxn], fac[maxn], ifc[maxn];
inline int32_t qpow (int32_t a, int32_t b = mod - 2) {
int64_t res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod, b >>= 1;
}
return res;
}
inline int32_t A (const int32_t x, const int32_t y) {
return 1ll * fac[x] * ifc[x - y] % mod;
}
int main () {
std::cin >> n >> k;
if (k == 1) return std::cout << 1 << '\n', 0;
f[0] = fac[0] = ifc[0] = 1;
for (int i = 1; i <= n; ++ i)
f[i] = fac[i] = 1ll * fac[i - 1] * i % mod;
ifc[n] = qpow (fac[n]);
for (int i = n - 1; i >= 1; -- i)
ifc[i] = 1ll * ifc[i + 1] * (i + 1) % mod;
for (int i = k + 1; i <= n; ++ i)
f[i] = (1ll * ((f[i - 1] - 1ll * f[i - k - 1] * A (i - 2, k - 1) % mod + mod) % mod) * i % mod + 1ll * f[i - k - 1] * A (i - 2, k - 1) % mod) % mod;
std::cout << f[n] << '\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3656kb
input:
1 1
output:
1
result:
ok "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 7736kb
input:
1 2
output:
1
result:
ok "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 7728kb
input:
1 3
output:
1
result:
ok "1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 7748kb
input:
1 4
output:
1
result:
ok "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
2 1
output:
1
result:
ok "1"
Test #6:
score: 0
Accepted
time: 1ms
memory: 7668kb
input:
2 2
output:
2
result:
ok "2"
Test #7:
score: 0
Accepted
time: 1ms
memory: 7820kb
input:
2 3
output:
2
result:
ok "2"
Test #8:
score: 0
Accepted
time: 1ms
memory: 7612kb
input:
2 4
output:
2
result:
ok "2"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
3 1
output:
1
result:
ok "1"
Test #10:
score: 0
Accepted
time: 0ms
memory: 7612kb
input:
3 2
output:
4
result:
ok "4"
Test #11:
score: 0
Accepted
time: 0ms
memory: 7612kb
input:
3 3
output:
6
result:
ok "6"
Test #12:
score: 0
Accepted
time: 1ms
memory: 7616kb
input:
3 4
output:
6
result:
ok "6"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
4 1
output:
1
result:
ok "1"
Test #14:
score: -100
Wrong Answer
time: 1ms
memory: 7748kb
input:
4 2
output:
171413171
result:
wrong answer 1st words differ - expected: '10', found: '171413171'