QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#958824#8147. Math ExamdsptAC ✓194ms184056kbC++231.1kb2025-03-31 10:40:262025-03-31 10:40:26

Judging History

This is the latest submission verdict.

  • [2025-03-31 10:40:26]
  • Judged
  • Verdict: AC
  • Time: 194ms
  • Memory: 184056kb
  • [2025-03-31 10:40:26]
  • Submitted

answer

#include <stdio.h>
const int p(998244353);
int n, f[10000001], g[10000001];
int abs(const int x) { return x > 0 ? x : -x; }
int comb(const int n, const int m) { return (long long)f[n] * g[m] % p * g[n - m] % p; }
int calc(const int a, const int b, int c, const bool d)
{
	if (!d)
	{
		c = (a << 1) - c;
		if (abs(c) > n) return 0;
		int w(comb(n, (n + abs(c)) >> 1));
		return (w - calc((a << 1) - b, a, c, 0) + p) % p;
	}
	else
	{
		c = (b << 1) - c;
		if (abs(c) > n) return 0;
		int w(comb(n, (n + abs(c)) >> 1));
		return (w - calc(b, (b << 1) - a, c, 1) + p) % p;
	}
}

int main()
{
	int m, w(0); scanf("%d%d", &n, &m); m = (m + 1) >> 1;
	f[0] = f[1] = g[0] = g[1] = 1;
	for (int i(2); i <= n; ++i)
	{
		f[i] = (long long)f[i - 1] * i % p;
		g[i] = (long long)(p - p / i) * g[p % i] % p;
	}
	for (int i(2); i <= n; ++i) g[i] = (long long)g[i - 1] * g[i] % p;
	--n;
	for (int i(-1); i < m; ++i) if ((i & 1) == (n & 1))
		w = ((w + comb(n, (n + abs(i)) >> 1) - calc(m, -2, i, 0) - calc(m, -2, i, 1)) % p + p) % p;
	return !printf("%d\n", w);
}

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

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3816kb

input:

9 13

output:

124

result:

ok answer is '124'

Test #2:

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

input:

500 999

output:

195157058

result:

ok answer is '195157058'

Test #3:

score: 0
Accepted
time: 183ms
memory: 79828kb

input:

10000000 19260817

output:

475124613

result:

ok answer is '475124613'

Test #4:

score: 0
Accepted
time: 20ms
memory: 13652kb

input:

1234567 654321

output:

986926700

result:

ok answer is '986926700'

Test #5:

score: 0
Accepted
time: 23ms
memory: 14536kb

input:

1145141 11451

output:

186897097

result:

ok answer is '186897097'

Test #6:

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

input:

114514 11451

output:

91839230

result:

ok answer is '91839230'

Test #7:

score: 0
Accepted
time: 19ms
memory: 13636kb

input:

1145143 114555

output:

641840034

result:

ok answer is '641840034'

Test #8:

score: 0
Accepted
time: 36ms
memory: 21968kb

input:

2123181 1980523

output:

784155222

result:

ok answer is '784155222'

Test #9:

score: 0
Accepted
time: 66ms
memory: 38768kb

input:

4238693 1876847

output:

169222558

result:

ok answer is '169222558'

Test #10:

score: 0
Accepted
time: 138ms
memory: 63976kb

input:

7804655 10519823

output:

935955279

result:

ok answer is '935955279'

Test #11:

score: 0
Accepted
time: 172ms
memory: 74352kb

input:

9189568 17055313

output:

811181659

result:

ok answer is '811181659'

Test #12:

score: 0
Accepted
time: 10ms
memory: 12220kb

input:

683534 1001003

output:

569208897

result:

ok answer is '569208897'

Test #13:

score: 0
Accepted
time: 30ms
memory: 17472kb

input:

1850342 3700683

output:

852266054

result:

ok answer is '852266054'

Test #14:

score: 0
Accepted
time: 163ms
memory: 79676kb

input:

10000000 1234567

output:

387622638

result:

ok answer is '387622638'

Test #15:

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

input:

1 1

output:

1

result:

ok answer is '1'

Test #16:

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

input:

3 1

output:

1

result:

ok answer is '1'

Test #17:

score: 0
Accepted
time: 194ms
memory: 184056kb

input:

10000000 1

output:

1

result:

ok answer is '1'

Extra Test:

score: 0
Extra Test Passed