QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#762841 | #8023. The Journey of Geor Autumn | Richard | AC ✓ | 133ms | 159892kb | C++17 | 1.2kb | 2024-11-19 16:57:06 | 2024-11-19 16:57:07 |
Judging History
answer
#include <bits/stdc++.h>
#define mod 998244353
#define File(xxx) freopen(xxx".in","r",stdin),freopen(xxx".out","w",stdout)
using namespace std;
typedef long long LL;
const int N = 1e7+5;
int n, k, jc[N], inv[N], a[N], sum[N];
template <typename T> inline void debug(T x) { cerr<<x; }
template <typename T, typename ...T_> inline void debug(T x, T_ ...p) { cerr<<x<<' ', debug(p...); }
template <typename T> void read(T& x) {
x = 0; int f = 0; char c = getchar();
while(c < '0' || c > '9') f |= (c == '-'), c=getchar();
while(c >= '0' && c <= '9') x=(x<<1)+(x<<3)+(c^48), c=getchar();
x=(f ? -x : x);
}
int lne; char put[105];
template <typename T> void write(T x, char ch) {
lne = 0; if(x < 0) putchar('-'), x=-x;
do { put[++lne]=x%10, x/=10; } while(x);
while(lne) putchar(put[lne--]^48);
putchar(ch);
}
int upd(int x) {
return (x >= mod ? x-mod : x);
}
signed main() {
read(n), read(k);
jc[0]=jc[1]=inv[0]=inv[1]=1;
for(int i = 2; i <= n; ++i)
jc[i]=1LL*jc[i-1]*i%mod, inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
a[0]=1;
sum[0]=1;
for(int i = 1; i <= n; ++i) {
a[i]=1LL*upd(sum[i-1]-(i > k ? sum[i-k-1] : 0)+mod)*inv[n-i]%mod;
sum[i]=upd(sum[i-1]+a[i]);
}
write(1LL*a[n]*jc[n-1]%mod, '\n');
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 9672kb
input:
1 1
output:
1
result:
ok "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 9796kb
input:
1 2
output:
1
result:
ok "1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 9788kb
input:
1 3
output:
1
result:
ok "1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 9868kb
input:
1 4
output:
1
result:
ok "1"
Test #5:
score: 0
Accepted
time: 1ms
memory: 9876kb
input:
2 1
output:
1
result:
ok "1"
Test #6:
score: 0
Accepted
time: 1ms
memory: 9872kb
input:
2 2
output:
2
result:
ok "2"
Test #7:
score: 0
Accepted
time: 0ms
memory: 9672kb
input:
2 3
output:
2
result:
ok "2"
Test #8:
score: 0
Accepted
time: 0ms
memory: 9848kb
input:
2 4
output:
2
result:
ok "2"
Test #9:
score: 0
Accepted
time: 0ms
memory: 9848kb
input:
3 1
output:
1
result:
ok "1"
Test #10:
score: 0
Accepted
time: 0ms
memory: 9804kb
input:
3 2
output:
4
result:
ok "4"
Test #11:
score: 0
Accepted
time: 1ms
memory: 9728kb
input:
3 3
output:
6
result:
ok "6"
Test #12:
score: 0
Accepted
time: 1ms
memory: 9804kb
input:
3 4
output:
6
result:
ok "6"
Test #13:
score: 0
Accepted
time: 1ms
memory: 9872kb
input:
4 1
output:
1
result:
ok "1"
Test #14:
score: 0
Accepted
time: 1ms
memory: 9728kb
input:
4 2
output:
10
result:
ok "10"
Test #15:
score: 0
Accepted
time: 1ms
memory: 9808kb
input:
4 3
output:
18
result:
ok "18"
Test #16:
score: 0
Accepted
time: 1ms
memory: 9792kb
input:
4 4
output:
24
result:
ok "24"
Test #17:
score: 0
Accepted
time: 0ms
memory: 9808kb
input:
99 50
output:
955866606
result:
ok "955866606"
Test #18:
score: 0
Accepted
time: 0ms
memory: 9800kb
input:
99 70
output:
296999003
result:
ok "296999003"
Test #19:
score: 0
Accepted
time: 1ms
memory: 9800kb
input:
1034 998
output:
637688669
result:
ok "637688669"
Test #20:
score: 0
Accepted
time: 1ms
memory: 9872kb
input:
1099 997
output:
712935289
result:
ok "712935289"
Test #21:
score: 0
Accepted
time: 1ms
memory: 9752kb
input:
10314 998
output:
224695890
result:
ok "224695890"
Test #22:
score: 0
Accepted
time: 1ms
memory: 9840kb
input:
10929 9974
output:
160291286
result:
ok "160291286"
Test #23:
score: 0
Accepted
time: 2ms
memory: 10208kb
input:
103124 99448
output:
695932649
result:
ok "695932649"
Test #24:
score: 0
Accepted
time: 2ms
memory: 10096kb
input:
109139 9937
output:
268916696
result:
ok "268916696"
Test #25:
score: 0
Accepted
time: 16ms
memory: 26380kb
input:
1031234 99238
output:
441457721
result:
ok "441457721"
Test #26:
score: 0
Accepted
time: 17ms
memory: 28716kb
input:
1091239 991237
output:
61047495
result:
ok "61047495"
Test #27:
score: 0
Accepted
time: 133ms
memory: 159892kb
input:
10000000 9982443
output:
224744113
result:
ok "224744113"
Test #28:
score: 0
Accepted
time: 117ms
memory: 159888kb
input:
9999977 5678901
output:
641748125
result:
ok "641748125"
Extra Test:
score: 0
Extra Test Passed