QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#312337#7754. Rolling For Days275307894aAC ✓129ms78616kbC++142.6kb2024-01-23 20:20:362024-01-23 20:20:37

Judging History

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

  • [2024-01-23 20:20:37]
  • 评测
  • 测评结果:AC
  • 用时:129ms
  • 内存:78616kb
  • [2024-01-23 20:20:36]
  • 提交

answer

#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=(1<<12)+5,M=1000+5,K=1000+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(263082);
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;

int n,m,k,sa[N],sb[N],A[N],B[N];ll frc[N],frv[N],inv[N],C[N][N];
ll dp[N][N][2],g[N][2];
ll mpow(ll x,int y=mod-2){ll ans=1;while(y) y&1&&(ans=ans*x%mod),y>>=1,x=x*x%mod;return ans;}
void Solve(){
	int i,j,h;scanf("%d%d",&n,&m);k=(1<<m);
	for(i=0;i<m;i++) scanf("%d",&A[i]);
	for(i=0;i<m;i++) scanf("%d",&B[i]);
	for(i=1;i<k;i++) sa[i]=sa[i^(i&-i)]+A[__lg(i&-i)];
	for(i=1;i<k;i++) sb[i]=sb[i^(i&-i)]+B[__lg(i&-i)];
	inv[1]=1;for(i=2;i<=n;i++) inv[i]=(mod-inv[mod%i])*(mod/i)%mod;
	for(frc[0]=frv[0]=i=1;i<=n;i++) frc[i]=frc[i-1]*i%mod,frv[i]=frv[i-1]*inv[i]%mod;
	for(i=0;i<=n;i++) for(C[i][0]=j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
	int goal=0;for(i=0;i<m;i++) if(!B[i]) goal|=1<<i;
	dp[goal][0][0]=1;
	for(i=0;i<k;i++){
		// for(h=0;h<=sb[k-1]-sb[i];h++) gdb(i,h,dp[i][h][0],dp[i][h][1]);
		for(j=0;j<m;j++)if(~i>>j&1){
			Mc(g,dp[i]);
			for(h=1;h<=sb[k-1]-sb[i];h++){
				g[h][0]=(g[h][0]+g[h-1][0]*inv[sa[k-1]-sa[i]-(h-1)])%mod;
				g[h][1]=(g[h-1][1]*inv[sa[k-1]-sa[i]-(h-1)]+g[h][1]+g[h-1][0]*inv[sa[k-1]-sa[i]-(h-1)]%mod*inv[sa[k-1]-sa[i]-(h-1)]%mod*(sa[k-1]-sb[i]-(h-1)))%mod;
				// gdb(inv[sa[k-1]-sa[i]-(h-1)]%mod);
			} 
			for(h=0;h<=sb[k-1]-sb[i];h++) g[h][0]=(g[h][0]+mod-dp[i][h][0])%mod,g[h][1]=(g[h][1]+mod-dp[i][h][1])%mod;
			for(h=B[j];h<=sb[k-1]-sb[i];h++){
				ll w=C[h-1][B[j]-1]*C[A[j]][B[j]]%mod*frc[B[j]]%mod;
				dp[i|(1<<j)][h-B[j]][0]=(dp[i|(1<<j)][h-B[j]][0]+g[h][0]*w)%mod;
				dp[i|(1<<j)][h-B[j]][1]=(dp[i|(1<<j)][h-B[j]][1]+g[h][1]*w)%mod;
			}
		}
	}	
	gdb(dp[k-1][0][1],dp[k-1][0][0]);
	printf("%lld\n",dp[k-1][0][1]*mpow(dp[k-1][0][0])%mod);
}
int main(){
	int t=1;
	// scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}

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

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 6136kb

input:

2 2
1 1
1 1

output:

2

result:

ok answer is '2'

Test #2:

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

input:

4 2
2 2
2 1

output:

582309210

result:

ok answer is '582309210'

Test #3:

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

input:

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

output:

5

result:

ok answer is '5'

Test #4:

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

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: 8180kb

input:

5 2
4 1
2 1

output:

598946616

result:

ok answer is '598946616'

Test #6:

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

input:

5 2
3 2
3 1

output:

482484776

result:

ok answer is '482484776'

Test #7:

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

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: 0ms
memory: 8200kb

input:

3 3
1 1 1
1 1 0

output:

499122180

result:

ok answer is '499122180'

Test #9:

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

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: 6156kb

input:

3 2
2 1
2 0

output:

499122180

result:

ok answer is '499122180'

Test #11:

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

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: 6264kb

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: 2ms
memory: 8276kb

input:

20 4
5 4 3 8
1 2 2 3

output:

156108321

result:

ok answer is '156108321'

Test #14:

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

input:

15 2
6 9
2 8

output:

672033760

result:

ok answer is '672033760'

Test #15:

score: 0
Accepted
time: 29ms
memory: 24680kb

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: 32ms
memory: 24632kb

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: 6116kb

input:

20 2
19 1
1 1

output:

299473325

result:

ok answer is '299473325'

Test #18:

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

input:

19 2
14 5
10 1

output:

497380388

result:

ok answer is '497380388'

Test #19:

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

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: 0ms
memory: 10220kb

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: 10096kb

input:

100 4
15 38 24 23
0 20 0 1

output:

635309463

result:

ok answer is '635309463'

Test #22:

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

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: 38ms
memory: 29704kb

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: 30ms
memory: 27396kb

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: 0ms
memory: 8204kb

input:

100 3
10 60 30
0 28 21

output:

261595276

result:

ok answer is '261595276'

Test #26:

score: 0
Accepted
time: 2ms
memory: 8148kb

input:

84 2
39 45
4 23

output:

897695217

result:

ok answer is '897695217'

Test #27:

score: 0
Accepted
time: 2ms
memory: 39052kb

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: 3ms
memory: 32796kb

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: 4ms
memory: 38892kb

input:

1000 2
374 626
175 591

output:

501708945

result:

ok answer is '501708945'

Test #30:

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

input:

701 1
701
413

output:

413

result:

ok answer is '413'

Test #31:

score: 0
Accepted
time: 124ms
memory: 72904kb

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: 53ms
memory: 62780kb

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: 0ms
memory: 36964kb

input:

1000 4
473 65 438 24
79 61 327 24

output:

491224221

result:

ok answer is '491224221'

Test #34:

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

input:

870 4
320 17 182 351
145 0 181 4

output:

664946681

result:

ok answer is '664946681'

Test #35:

score: 0
Accepted
time: 106ms
memory: 68044kb

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:

3888811

result:

ok answer is '3888811'

Test #36:

score: 0
Accepted
time: 122ms
memory: 73704kb

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: 85ms
memory: 69920kb

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: 129ms
memory: 78616kb

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: 114ms
memory: 75340kb

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: 115ms
memory: 72996kb

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