ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#185248 | #2718. 8.2t3 | wosile | 100 | 2493ms | 40268kb | C++ | 2.1kb | 2023-09-26 11:42:48 | 2023-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;
}
Details
小提示:点击横条可展开更详细的信息
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