QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#708578	#7754. Rolling For Days	Appleblue17	AC ✓	1886ms	56608kb	C++14	2.4kb	2024-11-04 00:09:58	2024-11-04 00:09:58

Judging History

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

[2024-11-04 00:09:58]
评测

测评结果：AC
用时：1886ms
内存：56608kb

查看

[2024-11-04 00:09:58]
提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1100,M=4400,mod=998244353;

int ksm(int a,int x){
	int tot=1;
	while(x){
		if(x & 1ll) tot=tot*a%mod;
		a=a*a%mod;
		x>>=1ll;
	}
	return tot;
}

int mul[N],inv[N];
void init(int lim){
	mul[0]=inv[0]=1;
	for(int i=1;i<=lim;i++) mul[i]=mul[i-1]*i%mod;
	inv[lim]=ksm(mul[lim],mod-2);
	for(int i=lim-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
int C(int m,int n){
	if(m<0 || n<0 || m<n) return 0;
	return mul[m]*inv[n]%mod*inv[m-n]%mod;
}
void gmod(int &x){
	x%=mod;
}

int n,m,alc=1;
int a[N],b[N];
int f[M][N],g[M][N];
int sumc[M],sumb[M];

inline int A(int t,int mac){
	return ksm(n-t-sumc[mac],mod-2);
}
inline int B(int t,int mac){
	return (n-t)*A(t,mac)%mod;
}

int a_[N],b_[N];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	init(N-5);
	cin>>n>>m;
	int ansmac=(1<<m)-1;
	for(int i=0;i<m;i++) cin>>a[i];
	for(int i=0;i<m;i++){
		cin>>b[i];
		if(!b[i]) ansmac^=1<<i;
	}
	
	for(int mac=0;mac<(1<<m);mac++){
		for(int i=0;i<m;i++){
			if(!(mac>>i & 1)){
				sumc[mac]+=a[i]-b[i];
				sumb[mac]+=b[i];
			}
		}
	}
	for(int i=0;i<m;i++) alc=alc*mul[a[i]]%mod*inv[a[i]-b[i]]%mod;
	
	f[0][0]=1;
	for(int mac=0;mac<(1<<m);mac++){
		// cout<<mac<<": "<<endl;
		for(int i=n;i>=0;i--){
			if(!f[mac][i] && !g[mac][i]) continue;
			// cout<<mac<<" "<<i<<": "<<endl;
			int t=sumb[mac]+i-1;
			if(i){
				int valA=A(t,mac),valB=B(t,mac);
				gmod(f[mac][i-1]+=f[mac][i]*valA%mod);
				gmod(g[mac][i-1]+=g[mac][i]*valA%mod);
				gmod(g[mac][i-1]+=f[mac][i]*valA%mod*valB%mod);
				// cout<<"   => "<<mac<<" "<<i-1<<" ("<<t<<", "<<A(t,mac)<<", "<<A(t,mac)*B(t,mac)%mod<<")"<<endl;
			}
			
			for(int x=0;x<m;x++){
				if(mac>>x & 1) continue;
				int nmac=mac | (1<<x);
				if(b[x]){
					int valA=C(i+b[x]-1,i)%mod*A(t,nmac)%mod,valB=B(t,nmac);
					gmod(f[nmac][i+b[x]-1]+=f[mac][i]*valA%mod);
					gmod(g[nmac][i+b[x]-1]+=g[mac][i]*valA%mod);
					gmod(g[nmac][i+b[x]-1]+=f[mac][i]*valA%mod*valB%mod);
					
					// cout<<t<<" "<<mac<<" "<<n-t-sumc[nmac]<<endl;
					// cout<<"   => "<<nmac<<" "<<i-1+b[x]<<" ("<<t<<", "<<C(i+b[x]-1,i)<<", "<<A(t,nmac)<<", "<<A(t,nmac)*B(t,nmac)%mod<<")"<<endl;
				}
			}
		}
		// for(int i=0;i<=n;i++) cout<<f[mac][i]<<" ";
		// cout<<endl;
		// for(int i=0;i<=n;i++) cout<<g[mac][i]<<" ";
		// cout<<endl;
	}
	cout<<g[ansmac][0]*alc%mod;
}

源文件, 语言: C++14

这程序好像有点Bug，我给组数据试试？

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 5708kb

input:

2 2
1 1
1 1

output:

result:

ok answer is '2'

Test #2:

score: 0

Accepted

time: 1ms

memory: 5704kb

input:

4 2
2 2
2 1

output:

582309210

result:

ok answer is '582309210'

Test #3:

score: 0

Accepted

time: 1ms

memory: 7648kb

input:

5 5
1 1 1 1 1
0 0 0 0 1

output:

result:

ok answer is '5'

Test #4:

score: 0

Accepted

time: 1ms

memory: 5684kb

input:

4 4
1 1 1 1
1 1 1 0

output:

831870299

result:

ok answer is '831870299'

Test #5:

score: 0

Accepted

time: 1ms

memory: 5732kb

input:

5 2
4 1
2 1

output:

598946616

result:

ok answer is '598946616'

Test #6:

score: 0

Accepted

time: 1ms

memory: 5800kb

input:

5 2
3 2
3 1

output:

482484776

result:

ok answer is '482484776'

Test #7:

score: 0

Accepted

time: 0ms

memory: 5688kb

input:

5 5
1 1 1 1 1
0 1 1 1 0

output:

665496242

result:

ok answer is '665496242'

Test #8:

score: 0

Accepted

time: 1ms

memory: 5724kb

input:

3 3
1 1 1
1 1 0

output:

499122180

result:

ok answer is '499122180'

Test #9:

score: 0

Accepted

time: 1ms

memory: 5888kb

input:

5 5
1 1 1 1 1
1 0 1 1 1

output:

582309212

result:

ok answer is '582309212'

Test #10:

score: 0

Accepted

time: 1ms

memory: 5660kb

input:

3 2
2 1
2 0

output:

499122180

result:

ok answer is '499122180'

Test #11:

score: 0

Accepted

time: 1ms

memory: 5776kb

input:

20 5
1 6 7 2 4
0 1 3 1 4

output:

75028873

result:

ok answer is '75028873'

Test #12:

score: 0

Accepted

time: 1ms

memory: 5840kb

input:

15 5
4 2 3 4 2
2 1 1 2 1

output:

585494868

result:

ok answer is '585494868'

Test #13:

score: 0

Accepted

time: 1ms

memory: 7772kb

input:

20 4
5 4 3 8
1 2 2 3

output:

156108321

result:

ok answer is '156108321'

Test #14:

score: 0

Accepted

time: 1ms

memory: 5704kb

input:

15 2
6 9
2 8

output:

672033760

result:

ok answer is '672033760'

Test #15:

score: 0

Accepted

time: 2ms

memory: 6328kb

input:

20 12
1 2 1 1 2 4 1 3 2 1 1 1
1 0 0 1 0 0 1 0 2 0 1 1

output:

691640771

result:

ok answer is '691640771'

Test #16:

score: 0

Accepted

time: 0ms

memory: 7696kb

input:

19 12
1 1 1 2 1 2 2 1 2 4 1 1
1 1 0 1 1 0 1 1 0 2 1 0

output:

777326448

result:

ok answer is '777326448'

Test #17:

score: 0

Accepted

time: 1ms

memory: 5672kb

input:

20 2
19 1
1 1

output:

299473325

result:

ok answer is '299473325'

Test #18:

score: 0

Accepted

time: 1ms

memory: 5748kb

input:

19 2
14 5
10 1

output:

497380388

result:

ok answer is '497380388'

Test #19:

score: 0

Accepted

time: 1ms

memory: 5716kb

input:

100 5
10 25 6 19 40
0 2 4 5 11

output:

773338801

result:

ok answer is '773338801'

Test #20:

score: 0

Accepted

time: 1ms

memory: 5668kb

input:

64 5
1 12 13 33 5
1 0 1 20 0

output:

571823997

result:

ok answer is '571823997'

Test #21:

score: 0

Accepted

time: 1ms

memory: 5732kb

input:

100 4
15 38 24 23
0 20 0 1

output:

635309463

result:

ok answer is '635309463'

Test #22:

score: 0

Accepted

time: 1ms

memory: 5828kb

input:

88 5
15 25 9 19 20
8 15 9 18 17

output:

400310961

result:

ok answer is '400310961'

Test #23:

score: 0

Accepted

time: 5ms

memory: 8748kb

input:

100 12
2 2 13 9 13 7 2 1 6 15 17 13
0 0 5 7 10 7 0 1 0 0 4 4

output:

552732942

result:

ok answer is '552732942'

Test #24:

score: 0

Accepted

time: 23ms

memory: 13628kb

input:

59 12
7 6 3 5 4 6 5 2 5 6 5 5
4 5 2 5 3 6 0 2 1 0 3 3

output:

27023521

result:

ok answer is '27023521'

Test #25:

score: 0

Accepted

time: 1ms

memory: 5704kb

input:

100 3
10 60 30
0 28 21

output:

261595276

result:

ok answer is '261595276'

Test #26:

score: 0

Accepted

time: 1ms

memory: 5664kb

input:

84 2
39 45
4 23

output:

897695217

result:

ok answer is '897695217'

Test #27:

score: 0

Accepted

time: 8ms

memory: 5904kb

input:

1000 5
370 136 129 182 183
312 47 112 22 119

output:

705415872

result:

ok answer is '705415872'

Test #28:

score: 0

Accepted

time: 0ms

memory: 5728kb

input:

766 5
372 194 98 90 12
165 123 53 27 0

output:

870555094

result:

ok answer is '870555094'

Test #29:

score: 0

Accepted

time: 1ms

memory: 5812kb

input:

1000 2
374 626
175 591

output:

501708945

result:

ok answer is '501708945'

Test #30:

score: 0

Accepted

time: 1ms

memory: 5700kb

input:

701 1
701
413

output:

result:

ok answer is '413'

Test #31:

score: 0

Accepted

time: 1886ms

memory: 56608kb

input:

1000 12
101 43 34 281 23 24 12 25 66 222 145 24
37 43 27 257 5 11 12 19 62 41 87 13

output:

265294941

result:

ok answer is '265294941'

Test #32:

score: 0

Accepted

time: 149ms

memory: 15244kb

input:

942 12
83 142 96 10 3 10 60 93 398 13 11 23
37 56 36 0 3 0 10 35 33 1 9 19

output:

956409637

result:

ok answer is '956409637'

Test #33:

score: 0

Accepted

time: 3ms

memory: 5732kb

input:

1000 4
473 65 438 24
79 61 327 24

output:

491224221

result:

ok answer is '491224221'

Test #34:

score: 0

Accepted

time: 1ms

memory: 5748kb

input:

870 4
320 17 182 351
145 0 181 4

output:

664946681

result:

ok answer is '664946681'

Test #35:

score: 0

Accepted

time: 667ms

memory: 29256kb

input:

1000 12
102 2 110 62 106 176 37 27 6 208 92 72
57 0 106 20 36 4 20 12 3 134 8 61

output:

result:

ok answer is '3888811'

Test #36:

score: 0

Accepted

time: 825ms

memory: 30680kb

input:

1000 12
1 44 209 187 27 71 127 139 134 22 20 19
0 19 153 113 27 29 82 74 37 19 20 9

output:

278584590

result:

ok answer is '278584590'

Test #37:

score: 0

Accepted

time: 1206ms

memory: 49768kb

input:

1000 12
193 84 261 36 75 7 70 12 38 22 8 194
68 15 11 20 16 7 53 1 6 6 6 189

output:

704313398

result:

ok answer is '704313398'

Test #38:

score: 0

Accepted

time: 974ms

memory: 32428kb

input:

1000 12
171 135 21 74 115 3 4 122 32 70 224 29
71 120 20 66 61 2 1 102 28 0 201 3

output:

608268027

result:

ok answer is '608268027'

Test #39:

score: 0

Accepted

time: 1757ms

memory: 56076kb

input:

1000 12
54 20 201 182 16 66 23 153 36 39 151 59
33 5 189 80 13 56 13 38 7 22 92 21

output:

795531860

result:

ok answer is '795531860'

Test #40:

score: 0

Accepted

time: 1690ms

memory: 55400kb

input:

1000 12
218 16 12 152 67 64 65 3 90 263 44 6
107 2 2 143 11 28 53 2 55 106 39 5

output:

903827471

result:

ok answer is '903827471'

Extra Test:

score: 0

Extra Test Passed