QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#415237#7632. Balanced Arrayszhangtx123AC ✓25ms27376kbC++141.9kb2024-05-20 16:52:342024-05-20 16:52:34

Judging History

你现在查看的是最新测评结果

  • [2024-05-20 16:52:34]
  • 评测
  • 测评结果:AC
  • 用时:25ms
  • 内存:27376kb
  • [2024-05-20 16:52:34]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
 #define debag(...) fprintf(stderr, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
 #define debag(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
#define mo 998244353
#define N 1000010
int pw(int a, int b) {
	int ans = 1; 
	while(b) {
		if(b & 1) ans *= a; 
		a *= a; b >>= 1; 
		ans %= mo; a %= mo; 
	}
	return ans; 
}
int pw(int a) { return pw(a, mo - 2); }
int fac[N], inv[N], ifac[N]; 
void init(int n) {
	int i; 
	for(i = fac[0] = 1; i <= n; ++i) fac[i] = fac[i-1] * i % mo; 
	ifac[n] = pw(fac[n], mo-2); 
	for(i = n - 1; i >= 0; --i) ifac[i] = ifac[i+1] * (i+1) % mo; 
    for(i = 1; i <= n; ++i) inv[i] = ifac[i] * fac[i-1] % mo; 
}
int C(int n, int m) {
	if(m > n) return 0;
	return fac[n] * ifac[m] % mo * ifac[n - m] % mo; 
}
inline void Mod(int &a) { if(a >= mo || a <= -mo) a %= mo; if(a < 0) a += mo; }
inline void Add(int &a, int b) { a += b; Mod(a); }
inline void Mul(int &a, int b) { Mod(b); a *= b; Mod(a); } 
const int iv2 = pw(2, mo - 2); 
int n, m, i, j, k, T;
int ans, o; 

int F(int n, int m) {
	if(m == 0) return 1; 
	int k = Z(C(n + m, m)) % mo - C(n + m, m - 1) * C(n + m, m + 1) % mo; 
	Mod(k); debug("[%lld %lld] %lld\n", n, m, k); 
	return Mod(k), k; 
}

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
//	T = read();
//	while(T--) {
//
//	}
	n = read(); m = read(); init(N - 1); 
	for(i = 0, o = 1; i <= min(n, m); ++i, o = -o) {
		Add(ans, o * F(n, m - i) * C(n, i) % mo); 
	}
	printf("%lld", ans); 
	return 0;
}

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

详细

Test #1:

score: 100
Accepted
time: 10ms
memory: 27128kb

input:

2 2

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 0
Accepted
time: 25ms
memory: 27240kb

input:

500000 500000

output:

984531374

result:

ok 1 number(s): "984531374"

Test #3:

score: 0
Accepted
time: 8ms
memory: 27128kb

input:

500000 1

output:

219705876

result:

ok 1 number(s): "219705876"

Test #4:

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

input:

1 500000

output:

500001

result:

ok 1 number(s): "500001"

Test #5:

score: 0
Accepted
time: 14ms
memory: 27164kb

input:

500000 353535

output:

33730077

result:

ok 1 number(s): "33730077"

Test #6:

score: 0
Accepted
time: 12ms
memory: 27232kb

input:

353535 500000

output:

182445298

result:

ok 1 number(s): "182445298"

Test #7:

score: 0
Accepted
time: 16ms
memory: 27248kb

input:

499999 499999

output:

933220940

result:

ok 1 number(s): "933220940"

Test #8:

score: 0
Accepted
time: 25ms
memory: 27316kb

input:

499999 499998

output:

899786345

result:

ok 1 number(s): "899786345"

Test #9:

score: 0
Accepted
time: 11ms
memory: 27248kb

input:

377773 400009

output:

206748715

result:

ok 1 number(s): "206748715"

Test #10:

score: 0
Accepted
time: 16ms
memory: 27312kb

input:

499999 100001

output:

482775773

result:

ok 1 number(s): "482775773"

Test #11:

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

input:

444445 488884

output:

70939759

result:

ok 1 number(s): "70939759"

Test #12:

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

input:

488885 444449

output:

591315327

result:

ok 1 number(s): "591315327"

Test #13:

score: 0
Accepted
time: 14ms
memory: 27248kb

input:

500000 111

output:

313439156

result:

ok 1 number(s): "313439156"

Test #14:

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

input:

333333 444444

output:

403492103

result:

ok 1 number(s): "403492103"

Test #15:

score: 0
Accepted
time: 16ms
memory: 27316kb

input:

499994 343433

output:

334451699

result:

ok 1 number(s): "334451699"

Test #16:

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

input:

477774 411113

output:

63883341

result:

ok 1 number(s): "63883341"

Test #17:

score: 0
Accepted
time: 8ms
memory: 27228kb

input:

123456 432109

output:

238795570

result:

ok 1 number(s): "238795570"

Test #18:

score: 0
Accepted
time: 15ms
memory: 27108kb

input:

131331 467777

output:

834790039

result:

ok 1 number(s): "834790039"

Test #19:

score: 0
Accepted
time: 4ms
memory: 27128kb

input:

500000 2

output:

304727284

result:

ok 1 number(s): "304727284"

Test #20:

score: 0
Accepted
time: 12ms
memory: 27312kb

input:

1111 111

output:

98321603

result:

ok 1 number(s): "98321603"

Test #21:

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

input:

416084 493105

output:

916827025

result:

ok 1 number(s): "916827025"

Test #22:

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

input:

53888 138663

output:

57263952

result:

ok 1 number(s): "57263952"

Test #23:

score: 0
Accepted
time: 17ms
memory: 27248kb

input:

219161 382743

output:

304889787

result:

ok 1 number(s): "304889787"

Test #24:

score: 0
Accepted
time: 14ms
memory: 27376kb

input:

181392 318090

output:

12528742

result:

ok 1 number(s): "12528742"

Test #25:

score: 0
Accepted
time: 12ms
memory: 27252kb

input:

135930 422947

output:

554153000

result:

ok 1 number(s): "554153000"

Test #26:

score: 0
Accepted
time: 12ms
memory: 27212kb

input:

280507 210276

output:

812816587

result:

ok 1 number(s): "812816587"

Test #27:

score: 0
Accepted
time: 11ms
memory: 27156kb

input:

253119 420465

output:

124024302

result:

ok 1 number(s): "124024302"

Test #28:

score: 0
Accepted
time: 12ms
memory: 27180kb

input:

446636 97448

output:

150388382

result:

ok 1 number(s): "150388382"

Test #29:

score: 0
Accepted
time: 15ms
memory: 27244kb

input:

284890 126665

output:

786559507

result:

ok 1 number(s): "786559507"

Test #30:

score: 0
Accepted
time: 12ms
memory: 27244kb

input:

186708 28279

output:

607509026

result:

ok 1 number(s): "607509026"

Extra Test:

score: 0
Extra Test Passed