QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#91623 | #4903. 细菌 | crashed | 100 ✓ | 804ms | 17712kb | C++14 | 4.8kb | 2023-03-29 10:24:01 | 2023-03-29 10:24:04 |
Judging History
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"