UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#185248#2718. 8.2t3wosile1002493ms40268kbC++2.1kb2023-09-26 11:42:482023-09-26 12:15:24

answer

#include<bits/stdc++.h>
using namespace std;
int n,m,Q;
map<int,int>ob;
#define mod 998244353
struct matrix{
	int a[4][4];
	void init0(){
		for(int i=0;i<n;i++)for(int j=0;j<n;j++)a[i][j]=0;
	}
	void output(){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++)printf("%d ",a[i][j]);
			printf("\n");
		}
	}
	void initdp(){
		init0();
		a[0][0]=1;
	}
	void init1(){
		init0();
		for(int i=0;i<n;i++)a[i][i]=1;
	}
	void itrans(int mask){
		init0();
		for(int i=0;i<n;i++){
			if((1<<i)&mask)continue;
			if(i>0 && ((1<<(i-1))&mask)==0)a[i][i-1]=1;
			if(i<n-1 && ((1<<(i+1))&mask)==0)a[i][i+1]=1;
		}
	}
	matrix operator *(const matrix &o)const{
		matrix ans;
		ans.init0();
		for(int i=0;i<n;i++)for(int j=0;j<n;j++)for(int k=0;k<n;k++)ans.a[i][j]=(ans.a[i][j]+1LL*a[i][k]*o.a[k][j])%mod;
		return ans;
	}
};
//4 10^9 10^5
set<int>ed;
matrix c[1500005];
const int N=200004;
matrix b;
matrix qp(int y){
	matrix ans;
	ans.init1();
	matrix x=b;
	while(y){
		if(y&1)ans=ans*x;
		x=x*x;
		y>>=1;
	}
	return ans;
}
int qx[100005],qy[100005];
int tmp[300005];
void build(int l,int r,int x){
//	printf("build %d %d %d\n",l,r,x);
	if(l==r){
//		printf("%d %d\n",tmp[l-1],tmp[l]);
		if(tmp[l-1]+1==tmp[l])c[x].itrans(ob[tmp[l]]);
		else c[x]=qp(tmp[l]-tmp[l-1]);
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,x<<1);
	build(mid+1,r,x<<1|1);
	c[x]=c[x<<1]*c[x<<1|1];
}
void update(int l,int r,int x,int pos){
	if(l==r){
//		printf("%d\n",pos);
		c[x].itrans(ob[tmp[l]]);
//		printf("ob %d\n",ob[tmp[l]]);
//		c[x].output();
		return;
	}
	int mid=(l+r)/2;
	if(pos<=mid)update(l,mid,x<<1,pos);
	else update(mid+1,r,x<<1|1,pos);
	c[x]=c[x<<1]*c[x<<1|1];
}
int main(){
	scanf("%d%d%d",&n,&m,&Q);
	b.itrans(0);
	for(int i=1;i<=Q;i++)scanf("%d%d",&qx[i],&qy[i]);
	int len=0;
	tmp[++len]=m;
	for(int i=1;i<=Q;i++){
		tmp[++len]=qy[i];
		if(qy[i]>1)tmp[++len]=qy[i]-1;
	}
	sort(tmp+1,tmp+len+1);
	len=unique(tmp+1,tmp+len+1)-tmp-1;
	build(1,len,1);
	for(int i=1;i<=Q;i++){
		ob[qy[i]]|=(1<<(qx[i]-1));
		int qwq=lower_bound(tmp+1,tmp+len+1,qy[i])-tmp;
		update(1,len,1,qwq);
		printf("%d\n",c[1].a[0][n-1]);
	}
	return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 1256kb

input:

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

output:

2
2
1
1
0

result:

ok 5 number(s): "2 2 1 1 0"

Test #2:

score: 10
Accepted
time: 243ms
memory: 22852kb

input:

2 99999 100000
2 70567
1 17791
2 77890
2 12623
2 13544
1 18390
2 8888
1 74050
2 67101
1 56764
2 3761...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 100000 numbers

Test #3:

score: 10
Accepted
time: 0ms
memory: 1260kb

input:

3 1000 5
3 805
3 596
3 575
3 58
3 577

output:

154029661
576137007
787190680
393595340
196797670

result:

ok 5 number(s): "154029661 576137007 787190680 393595340 196797670"

Test #4:

score: 10
Accepted
time: 0ms
memory: 1440kb

input:

3 1000 1000
1 45
3 898
1 799
1 48
1 847
3 607
1 760
1 802
3 903
3 836
1 526
3 264
1 96
3 244
3 242
3...

output:

154029661
576137007
787190680
393595340
196797670
98398835
548321594
274160797
636202575
817223464
4...

result:

ok 1000 numbers

Test #5:

score: 10
Accepted
time: 322ms
memory: 22848kb

input:

3 100000 100000
1 74197
3 11259
3 65940
3 1906
3 40328
1 71201
1 50943
1 98978
1 70015
3 43996
1 114...

output:

159434530
79717265
538980809
768612581
883428467
940836410
470418205
734331279
866287816
433143908
2...

result:

ok 100000 numbers

Test #6:

score: 10
Accepted
time: 322ms
memory: 22860kb

input:

3 100000 100000
1 16644
3 29648
3 77047
1 94435
1 43985
1 89629
1 78236
1 93267
3 25517
1 52560
1 89...

output:

159434530
79717265
538980809
768612581
883428467
940836410
470418205
734331279
866287816
433143908
2...

result:

ok 100000 numbers

Test #7:

score: 10
Accepted
time: 0ms
memory: 1292kb

input:

3 1000000000 100
1 574043575
1 413916829
3 96
1 394696238
1 40
3 38
1 69
1 968879034
1 52
1 62558778...

output:

745547840
372773920
186386960
93193480
46596740
23298370
11649185
504946769
751595561
874919957
9365...

result:

ok 100 numbers

Test #8:

score: 10
Accepted
time: 463ms
memory: 40220kb

input:

3 1000000000 100000
3 15019
1 79221
3 22394
1 89278
3 875067515
1 15404
1 615238057
3 89925
3 271777...

output:

745547840
372773920
186386960
93193480
46596740
23298370
11649185
504946769
751595561
874919957
9365...

result:

ok 100000 numbers

Test #9:

score: 10
Accepted
time: 263ms
memory: 21356kb

input:

4 99999 50000
4 66854
4 48295
4 95292
4 86389
4 9961
4 33406
4 96945
4 64418
4 19331
4 71257
4 36656...

output:

636299371
215744819
252527760
691521797
334927651
491663361
2328689
543779237
706792728
577050832
33...

result:

ok 50000 numbers

Test #10:

score: 10
Accepted
time: 880ms
memory: 40268kb

input:

4 999999999 100000
4 908546081
4 885383980
4 37966517
4 191661556
4 107475378
4 699076844
4 58764448...

output:

991199402
576071352
289809637
863841042
998188739
377996189
808622907
336679175
553400478
673609116
...

result:

ok 100000 numbers