QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#91623#4903. 细菌crashed100 ✓804ms17712kbC++144.8kb2023-03-29 10:24:012023-03-29 10:24:04

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-29 10:24:04]
  • 评测
  • 测评结果:100
  • 用时:804ms
  • 内存:17712kb
  • [2023-03-29 10:24:01]
  • 提交

answer

#include <cstdio>
#include <vector>
#include <algorithm>

#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )

const int mod = 998244353;
const int MAXN = ( 1 << 19 ) + 5;

template<typename _T>
inline void Read( _T &x ) {
	x = 0; char s = getchar(); bool f = false;
	while( ! ( '0' <= s && s <= '9' ) ) { f = s == '-', s = getchar(); }
	while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
	if( f ) x = -x;
}

template<typename _T>
inline void Write( _T x ) {
	if( x < 0 ) putchar( '-' ), x = -x;
	if( 9 < x ) Write( x / 10 );
	putchar( x % 10 + '0' );
}

template<typename _T>
inline _T Abs( const _T &x ) {
	return x < 0 ? -x : x;
}

int F1[MAXN], F2[MAXN], F3[MAXN];
int fac[MAXN], ifac[MAXN];

int ways[MAXN], tmp[MAXN];

inline int Qkpow( int, int );
inline int Inv( const int &a ) { return Qkpow( a, mod - 2 ); }
inline int Mul( int x, const int &v ) { return 1ll * x * v % mod; }
inline int Sub( int x, const int &v ) { return ( x -= v ) < 0 ? x + mod : x; }
inline int Add( int x, const int &v ) { return ( x += v ) >= mod ? x - mod : x; }

inline int& MulEq( int &x, const int &v ) { return x = 1ll * x * v % mod; }
inline int& SubEq( int &x, const int &v ) { return ( x -= v ) < 0 ? ( x += mod ) : x; }
inline int& AddEq( int &x, const int &v ) { return ( x += v ) >= mod ? ( x -= mod ) : x; }

inline int C( int n, int m ) { return n < m || m < 0 ? 0 : Mul( fac[n], Mul( ifac[m], ifac[n - m] ) ); }

inline int Qkpow( int base, int indx ) {
	int ret = 1;
	while( indx ) {
		if( indx & 1 ) MulEq( ret, base );
		MulEq( base, base ), indx >>= 1;
	}
	return ret;
}

namespace Basics {
	const int L = 19, g = 3, phi = mod - 1;

	int w[MAXN];

	inline void NTTInit( const int &n = 1 << L ) {
		w[0] = 1, w[1] = Qkpow( g, phi >> L );
		rep( i, 2, n - 1 ) w[i] = Mul( w[i - 1], w[1] );
	}

	inline void DIF( int *coe, const int &n ) {
		int *wp, p, e, o;
		for( int s = n >> 1 ; s ; s >>= 1 )
			for( int i = 0 ; i < n ; i += s << 1 ) {
				p = ( 1 << L ) / ( s << 1 ), wp = w;
				for( int j = 0 ; j < s ; j ++, wp += p ) {
					e = coe[i + j], o = coe[i + j + s];
					coe[i + j] = Add( e, o );
					coe[i + j + s] = Mul( *wp, Sub( e, o ) );
				}
			}
	}

	inline void DIT( int *coe, const int &n ) {
		int *wp, p, k;
		for( int s = 1 ; s < n ; s <<= 1 )
			for( int i = 0 ; i < n ; i += s << 1 ) {
				p = ( 1 << L ) / ( s << 1 ), wp = w;
				for( int j = 0 ; j < s ; j ++, wp += p )
					k = Mul( *wp, coe[i + j + s] ),
					coe[i + j + s] = Sub( coe[i + j], k ),
					coe[i + j] = Add( coe[i + j], k );
			}
		std :: reverse( coe + 1, coe + n );
		int inv = Inv( n ); rep( i, 0, n - 1 ) MulEq( coe[i], inv );
	}
}

inline void Init( const int &n ) {
	fac[0] = 1; rep( i, 1, n ) fac[i] = Mul( fac[i - 1], i );
	ifac[n] = Inv( fac[n] ); per( i, n - 1, 0 ) ifac[i] = Mul( ifac[i + 1], i + 1 );
}

inline int Free( const int &d, const int &a, const int &b ) {
	if( Abs( b - a ) % 2 != d % 2 ) return 0;
	int x = ( d + b - a ) >> 1, y = ( d - b + a ) >> 1;
	return C( x + y, x );
}

inline int Hitless( const int &d, const int &n, const int &a, const int &b ) {
	int ret = Free( d, a, b );
	if( ! ret ) return 0;
	for( int k = 0 ; Abs( 2 * ( k + 1 ) * ( n + 1 ) - b - a ) <= d ; k ++ )
		SubEq( ret, Free( d, a, 2 * ( k + 1 ) * ( n + 1 ) - b ) );
	for( int k = 0 ; Abs( - 2 * k * ( n + 1 ) - b - a ) <= d ; k ++ )
		SubEq( ret, Free( d, a, - 2 * k * ( n + 1 ) - b ) );
	for( int k = 1 ; Abs( b - 2 * k * ( n + 1 ) - a ) <= d ; k ++ )
		AddEq( ret, Free( d, a, b - 2 * k * ( n + 1 ) ) );
	for( int k = 1 ; Abs( b + 2 * k * ( n + 1 ) - a ) <= d ; k ++ )
		AddEq( ret, Free( d, a, b + 2 * k * ( n + 1 ) ) );
	return ret;
}

inline void MonoDim( int *ret, const int &d, const int &n, const int &a ) {
	if( 1ll * n * n <= a ) {
	// if( n <= 0 ) {
		rep( i, 0, n + 1 ) ways[i] = 0;
		ways[a] = ret[0] = 1;
		rep( i, 1, d ) {
			ret[i] = 0;
			rep( j, 1, n ) tmp[j] = Add( ways[j - 1], ways[j + 1] );
			rep( j, 1, n ) AddEq( ret[i], ways[j] = tmp[j] );
		}
	} else {
		ret[0] = 1;
		rep( i, 1, d ) 
			ret[i] = Sub( Mul( ret[i - 1], 2 ), Add( Hitless( i - 1, n, a, 1 ), Hitless( i - 1, n, a, n ) ) );
	}
}

int main() {
	int D, N, M, K, A, B, C;
	Read( D ), Read( N ), Read( M ), Read( K ), Read( A ), Read( B ), Read( C );
	Init( D ), Basics :: NTTInit();
	MonoDim( F1, D, N, A );
	MonoDim( F2, D, M, B );
	MonoDim( F3, D, K, C );
	rep( i, 0, D ) {
		MulEq( F1[i], ifac[i] );
		MulEq( F2[i], ifac[i] );
		MulEq( F3[i], ifac[i] );
	}
	int L = 1; for( ; L <= 3 * D ; L <<= 1 );
	Basics :: DIF( F1, L );
	Basics :: DIF( F2, L );
	Basics :: DIF( F3, L );
	rep( i, 0, L - 1 ) F1[i] = Mul( F1[i], Mul( F2[i], F3[i] ) );
	Basics :: DIT( F1, L );
	Write( Mul( fac[D], F1[D] ) ), putchar( '\n' );
	return 0;
}

详细

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 6ms
memory: 13736kb

input:

50 41 46 42 8 20 21

output:

791406134

result:

ok 1 number(s): "791406134"

Test #2:

score: 0
Accepted
time: 7ms
memory: 14412kb

input:

50 49 44 48 49 15 25

output:

544847893

result:

ok 1 number(s): "544847893"

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #3:

score: 10
Accepted
time: 2ms
memory: 14152kb

input:

5000 4994 4990 4990 976 2257 2505

output:

836390717

result:

ok 1 number(s): "836390717"

Test #4:

score: 0
Accepted
time: 9ms
memory: 14456kb

input:

5000 4994 4997 4994 4399 1826 1332

output:

65414465

result:

ok 1 number(s): "65414465"

Subtask #3:

score: 15
Accepted

Test #5:

score: 15
Accepted
time: 305ms
memory: 17648kb

input:

120000 300 1 1 141 1 1

output:

637174

result:

ok 1 number(s): "637174"

Test #6:

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

input:

120000 994 1 1 15 1 1

output:

218803691

result:

ok 1 number(s): "218803691"

Test #7:

score: 0
Accepted
time: 59ms
memory: 17708kb

input:

120000 119999 1 1 19896 1 1

output:

68846585

result:

ok 1 number(s): "68846585"

Subtask #4:

score: 10
Accepted

Test #8:

score: 10
Accepted
time: 60ms
memory: 17704kb

input:

119000 119991 119991 1 23819 52139 1

output:

944500934

result:

ok 1 number(s): "944500934"

Subtask #5:

score: 15
Accepted

Dependency #4:

100%
Accepted

Test #9:

score: 15
Accepted
time: 71ms
memory: 17712kb

input:

120000 13997 13996 1 42 9266 1

output:

775637357

result:

ok 1 number(s): "775637357"

Test #10:

score: 0
Accepted
time: 78ms
memory: 17632kb

input:

120000 13997 13997 1 9768 6131 1

output:

151873213

result:

ok 1 number(s): "151873213"

Subtask #6:

score: 35
Accepted

Dependency #3:

100%
Accepted

Dependency #5:

100%
Accepted

Test #11:

score: 35
Accepted
time: 546ms
memory: 17708kb

input:

120000 294 296 1 142 273 1

output:

889786082

result:

ok 1 number(s): "889786082"

Test #12:

score: 0
Accepted
time: 432ms
memory: 17600kb

input:

120000 395 390 1 370 185 1

output:

884557050

result:

ok 1 number(s): "884557050"

Test #13:

score: 0
Accepted
time: 360ms
memory: 17620kb

input:

120000 491 495 1 430 25 1

output:

272929924

result:

ok 1 number(s): "272929924"

Test #14:

score: 0
Accepted
time: 308ms
memory: 17648kb

input:

120000 590 593 1 418 459 1

output:

446962505

result:

ok 1 number(s): "446962505"

Test #15:

score: 0
Accepted
time: 292ms
memory: 17712kb

input:

120000 697 690 1 166 450 1

output:

216092107

result:

ok 1 number(s): "216092107"

Test #16:

score: 0
Accepted
time: 251ms
memory: 17708kb

input:

120000 793 799 1 416 61 1

output:

661260042

result:

ok 1 number(s): "661260042"

Test #17:

score: 0
Accepted
time: 214ms
memory: 17684kb

input:

120000 1000 1000 1 613 547 1

output:

429669083

result:

ok 1 number(s): "429669083"

Test #18:

score: 0
Accepted
time: 135ms
memory: 17712kb

input:

120000 1993 1995 1 493 565 1

output:

609392900

result:

ok 1 number(s): "609392900"

Test #19:

score: 0
Accepted
time: 95ms
memory: 17704kb

input:

120000 4995 4998 1 3166 3765 1

output:

394497547

result:

ok 1 number(s): "394497547"

Test #20:

score: 0
Accepted
time: 86ms
memory: 17700kb

input:

120000 9994 9991 1 6099 691 1

output:

795651799

result:

ok 1 number(s): "795651799"

Test #21:

score: 0
Accepted
time: 71ms
memory: 17588kb

input:

120000 49990 49990 1 41933 2862 1

output:

360787513

result:

ok 1 number(s): "360787513"

Test #22:

score: 0
Accepted
time: 74ms
memory: 17604kb

input:

120000 119996 119994 1 58014 49559 1

output:

682979057

result:

ok 1 number(s): "682979057"

Subtask #7:

score: 10
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #6:

100%
Accepted

Test #23:

score: 10
Accepted
time: 804ms
memory: 15548kb

input:

120000 296 300 297 89 130 280

output:

702788425

result:

ok 1 number(s): "702788425"

Test #24:

score: 0
Accepted
time: 608ms
memory: 15600kb

input:

120000 392 397 391 222 280 10

output:

322470184

result:

ok 1 number(s): "322470184"

Test #25:

score: 0
Accepted
time: 503ms
memory: 15600kb

input:

120000 499 498 500 263 315 367

output:

449848666

result:

ok 1 number(s): "449848666"

Test #26:

score: 0
Accepted
time: 434ms
memory: 15560kb

input:

120000 598 591 594 497 474 400

output:

35486519

result:

ok 1 number(s): "35486519"

Test #27:

score: 0
Accepted
time: 376ms
memory: 15540kb

input:

120000 694 692 695 625 173 477

output:

785203749

result:

ok 1 number(s): "785203749"

Test #28:

score: 0
Accepted
time: 337ms
memory: 15656kb

input:

120000 794 796 800 395 465 507

output:

897269426

result:

ok 1 number(s): "897269426"

Test #29:

score: 0
Accepted
time: 280ms
memory: 15656kb

input:

120000 993 998 991 196 712 911

output:

464727191

result:

ok 1 number(s): "464727191"

Test #30:

score: 0
Accepted
time: 176ms
memory: 15584kb

input:

120000 1991 2000 1994 1937 1362 1494

output:

473701811

result:

ok 1 number(s): "473701811"

Test #31:

score: 0
Accepted
time: 113ms
memory: 15580kb

input:

120000 4994 4990 4990 646 1214 2276

output:

763540821

result:

ok 1 number(s): "763540821"

Test #32:

score: 0
Accepted
time: 85ms
memory: 15600kb

input:

120000 9994 9992 9991 6588 9538 2632

output:

804858722

result:

ok 1 number(s): "804858722"

Test #33:

score: 0
Accepted
time: 69ms
memory: 15652kb

input:

120000 49997 49997 49993 46278 44140 26931

output:

139550295

result:

ok 1 number(s): "139550295"

Test #34:

score: 0
Accepted
time: 64ms
memory: 15652kb

input:

120000 119997 120000 120000 24867 116477 35338

output:

946147605

result:

ok 1 number(s): "946147605"