QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#762178#8023. The Journey of Geor AutumnCorzicaAC ✓215ms159952kbC++201023b2024-11-19 14:03:232024-11-19 14:03:26

Judging History

This is the latest submission verdict.

  • [2024-11-19 14:03:26]
  • Judged
  • Verdict: AC
  • Time: 215ms
  • Memory: 159952kb
  • [2024-11-19 14:03:23]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
int n, m;
const int mod = 998244353;
int f[10000007], sum[10000007], inv[10000007], jie[10000007];
inline int ksm(int p, int q = mod - 2) {
	int base = 1;
	while (q) {
		if (q & 1)base = base * 1ll * p % mod;
		q >>= 1;
		p = p * 1ll * p % mod;
	}
	return base;
}
signed main() {
//	freopen("b.in", "r", stdin);
//	freopen("b.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	f[0] = 1;
	jie[0] = 1;
	for (int i = 1; i <= n; i++) jie[i] = jie[i - 1] * 1ll * i % mod;
	inv[n] = ksm(jie[n]);
	for (int i = n - 1; i >= 0; i--) {
		inv[i] = (i + 1) * 1ll * inv[i + 1] % mod;
	}
	sum[0] = jie[n - 1] * 1ll * inv[n] % mod;
	for (int i = 1; i <= n; i++) {
		f[i] = sum[i - 1];
		if (i - m - 1 >= 0) {
			f[i] = (f[i] - sum[i - m - 1] + mod) % mod;
		}
		if (i ^ n)	sum[i] = f[i] * 1ll * jie[n - i - 1] % mod * inv[n - i] % mod;
		sum[i] = (sum[i] + sum[i - 1]) % mod;
	}
	cout << f[n] * 1ll * jie[n] % mod;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 9736kb

input:

1 1

output:

1

result:

ok "1"

Test #2:

score: 0
Accepted
time: 1ms
memory: 9692kb

input:

1 2

output:

1

result:

ok "1"

Test #3:

score: 0
Accepted
time: 1ms
memory: 9680kb

input:

1 3

output:

1

result:

ok "1"

Test #4:

score: 0
Accepted
time: 1ms
memory: 9852kb

input:

1 4

output:

1

result:

ok "1"

Test #5:

score: 0
Accepted
time: 1ms
memory: 9800kb

input:

2 1

output:

1

result:

ok "1"

Test #6:

score: 0
Accepted
time: 0ms
memory: 9748kb

input:

2 2

output:

2

result:

ok "2"

Test #7:

score: 0
Accepted
time: 1ms
memory: 9852kb

input:

2 3

output:

2

result:

ok "2"

Test #8:

score: 0
Accepted
time: 1ms
memory: 9736kb

input:

2 4

output:

2

result:

ok "2"

Test #9:

score: 0
Accepted
time: 1ms
memory: 9800kb

input:

3 1

output:

1

result:

ok "1"

Test #10:

score: 0
Accepted
time: 1ms
memory: 9740kb

input:

3 2

output:

4

result:

ok "4"

Test #11:

score: 0
Accepted
time: 1ms
memory: 9744kb

input:

3 3

output:

6

result:

ok "6"

Test #12:

score: 0
Accepted
time: 1ms
memory: 9680kb

input:

3 4

output:

6

result:

ok "6"

Test #13:

score: 0
Accepted
time: 1ms
memory: 9852kb

input:

4 1

output:

1

result:

ok "1"

Test #14:

score: 0
Accepted
time: 1ms
memory: 9812kb

input:

4 2

output:

10

result:

ok "10"

Test #15:

score: 0
Accepted
time: 1ms
memory: 9788kb

input:

4 3

output:

18

result:

ok "18"

Test #16:

score: 0
Accepted
time: 0ms
memory: 9804kb

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: 1ms
memory: 9792kb

input:

99 70

output:

296999003

result:

ok "296999003"

Test #19:

score: 0
Accepted
time: 1ms
memory: 9860kb

input:

1034 998

output:

637688669

result:

ok "637688669"

Test #20:

score: 0
Accepted
time: 1ms
memory: 9876kb

input:

1099 997

output:

712935289

result:

ok "712935289"

Test #21:

score: 0
Accepted
time: 1ms
memory: 9776kb

input:

10314 998

output:

224695890

result:

ok "224695890"

Test #22:

score: 0
Accepted
time: 1ms
memory: 9912kb

input:

10929 9974

output:

160291286

result:

ok "160291286"

Test #23:

score: 0
Accepted
time: 3ms
memory: 10132kb

input:

103124 99448

output:

695932649

result:

ok "695932649"

Test #24:

score: 0
Accepted
time: 0ms
memory: 10216kb

input:

109139 9937

output:

268916696

result:

ok "268916696"

Test #25:

score: 0
Accepted
time: 28ms
memory: 27472kb

input:

1031234 99238

output:

441457721

result:

ok "441457721"

Test #26:

score: 0
Accepted
time: 27ms
memory: 27160kb

input:

1091239 991237

output:

61047495

result:

ok "61047495"

Test #27:

score: 0
Accepted
time: 208ms
memory: 159952kb

input:

10000000 9982443

output:

224744113

result:

ok "224744113"

Test #28:

score: 0
Accepted
time: 215ms
memory: 159840kb

input:

9999977 5678901

output:

641748125

result:

ok "641748125"

Extra Test:

score: 0
Extra Test Passed