QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#379984 | #3082. Ascending Matrix | xlwang | TL | 1506ms | 10024kb | C++14 | 6.0kb | 2024-04-06 20:23:36 | 2024-04-06 20:23:36 |
Judging History
answer
// #define fastcall __attribute__((optimize("-O3")))
// #pragma GCC optimize(1)
// #pragma GCC optimize(2)
// #pragma GCC optimize(3)
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("inline")
// #pragma GCC optimize("-fgcse")
// #pragma GCC optimize("-fgcse-lm")
// #pragma GCC optimize("-fipa-sra")
// #pragma GCC optimize("-ftree-pre")
// #pragma GCC optimize("-ftree-vrp")
// #pragma GCC optimize("-fpeephole2")
// #pragma GCC optimize("-ffast-math")
// #pragma GCC optimize("-fsched-spec")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("-falign-jumps")
// #pragma GCC optimize("-falign-loops")
// #pragma GCC optimize("-falign-labels")
// #pragma GCC optimize("-fdevirtualize")
// #pragma GCC optimize("-fcaller-saves")
// #pragma GCC optimize("-fcrossjumping")
// #pragma GCC optimize("-fthread-jumps")
// #pragma GCC optimize("-funroll-loops")
// #pragma GCC optimize("-fwhole-program")
// #pragma GCC optimize("-freorder-blocks")
// #pragma GCC optimize("-fschedule-insns")
// #pragma GCC optimize("inline-functions")
// #pragma GCC optimize("-ftree-tail-merge")
// #pragma GCC optimize("-fschedule-insns2")
// #pragma GCC optimize("-fstrict-aliasing")
// #pragma GCC optimize("-fstrict-overflow")
// #pragma GCC optimize("-falign-functions")
// #pragma GCC optimize("-fcse-skip-blocks")
// #pragma GCC optimize("-fcse-follow-jumps")
// #pragma GCC optimize("-fsched-interblock")
// #pragma GCC optimize("-fpartial-inlining")
// #pragma GCC optimize("no-stack-protector")
// #pragma GCC optimize("-freorder-functions")
// #pragma GCC optimize("-findirect-inlining")
// #pragma GCC optimize("-fhoist-adjacent-loads")
// #pragma GCC optimize("-frerun-cse-after-loop")
// #pragma GCC optimize("inline-small-functions")
// #pragma GCC optimize("-finline-small-functions")
// #pragma GCC optimize("-ftree-switch-conversion")
// #pragma GCC optimize("-foptimize-sibling-calls")
// #pragma GCC optimize("-fexpensive-optimizations")
// #pragma GCC optimize("-funsafe-loop-optimizations")
// #pragma GCC optimize("inline-functions-called-once")
// #pragma GCC optimize("-fdelete-null-pointer-checks")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include<bits/stdc++.h>
#define fr(i,j,k) for(register int i=j;i<=k;++i)
#define rf(i,j,k) for(register int i=j;i>=k;--i)
#define foredge(i,j) for(register int i=head[j];i;i=e[i].nxt)
#define pb push_back
#define Times printf("Time:%.3lf\n",clock()/CLOCKS_PER_SEC)
using namespace std;
inline int read(){
int x=0;
bool f=0;
char c=getchar();
while(!isdigit(c)) f|=(c=='-'),c=getchar();
while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
return f?-x:x;
}
inline void write(int x){
if(x<0){putchar('-');x=-x;}
if(x>9)write(x/10);
putchar(x%10+'0');
}
inline void writeln(int x){write(x); puts("");}
inline void writepl(int x){write(x); putchar(' ');}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline int randfind(int l,int r){return rnd()%(r-l+1)+l;}
//inline void init(){
// int t=read();
// while(t--) work();
//}
const int Maxn=5e2+10,mod=998244353;
inline int ksm(int x,int y=mod-2){
int sum=1;
while(y){
if(y&1) sum=1ll*sum*x%mod;
y=y/2;x=1ll*x*x%mod;
}
return sum;
}
inline void add(int &x,int y){
x+=y;if(x>=mod) x-=mod;
}
int n,m,k,r,c,v;
int vis[Maxn][Maxn];
int K[Maxn][Maxn],B[Maxn][Maxn];
inline void init(){
n=read();m=read();k=read();r=read();c=read();v=read();
fr(i,1,r+v-1) fr(j,1,c+v-1) vis[i][j]=1;
}
int f[Maxn][Maxn][2];
inline void clear(){
fr(i,0,n+k) fr(j,0,m+k) f[i][j][0]=f[i][j][1]=0;
}
inline void dp(int x,int y){
rf(i,n+x,1) fr(j,1,m+y){
if(vis[i][j]) add(f[i][j][1],f[i][j][0]),f[i][j][0]=0;
if(i==r+v-1 && j==c+v-1) f[i][j][1]=0;
add(f[i-1][j][0],f[i][j][0]);add(f[i-1][j][1],f[i][j][1]);
add(f[i][j+1][0],f[i][j][0]);add(f[i][j+1][1],f[i][j][1]);
}
}
int a[Maxn][Maxn];
int value[Maxn][Maxn];
inline int getval(){
int tp=1;
fr(i,1,k){
fr(j,i+1,k){
if(value[i][i]){
int num=1ll*ksm(value[j][i])*value[i][i]%mod;
fr(l,i,k) add(value[i][l],mod-1ll*value[j][l]*num%mod);
}
if(!value[i][i]){
fr(l,i,k) swap(value[i][l],value[j][l]);
tp*=-1;
}
}
}
int ans;
if(tp==1) ans=1;
else ans=mod-1;
fr(i,1,k) ans=1ll*ans*value[i][i]%mod;
return ans;
}
inline void into(int val){
fr(i,0,k) a[val][i]=ksm(val,i);
fr(i,1,k) fr(j,1,k) value[i][j]=1ll*K[i][j]*val%mod,add(value[i][j],B[i][j]);
a[val][k+1]=getval();
}
int x[Maxn];
inline void update(){
fr(i,0,k){
int id=i;
fr(j,i,k) if(a[j][i]>a[id][i]) id=j;
swap(a[id],a[i]);
int inum=ksm(a[i][i]);
fr(j,i+1,k+1){
int now=1ll*inum*a[j][i]%mod;
fr(l,i,k+1) add(a[j][l],mod-1ll*a[i][l]*now%mod);
}
}
// fr(i,0,k+1){
// fr(j,0,k+2) cout<<a[i][j]<<' ';
// cout<<endl;
// }
rf(i,k+1,0){
fr(j,i+1,k+1) add(a[i][k+1],mod-1ll*a[i][j]*x[j]%mod);
x[i]=1ll*a[i][k+1]*ksm(a[i][i])%mod;
}
// fr(i,0,k+1) cout<<i<<' '<<x[i]<<endl;
}
inline void work(){
--k;
// printf("\nTIME:%.3lf",(double)clock()/CLOCKS_PER_SEC);
fr(i,1,k) fr(j,1,k){
clear();f[n+i][i][0]=1;
dp(i,j);
K[i][j]=f[j][j+m][1],B[i][j]=f[j][j+m][0];
}
// fr(i,1,k) fr(j,1,k) cout<<i<<' '<<j<<' '<<K[i][j]<<' '<<B[i][j]<<endl;
// printf("\nTIME:%.3lf",(double)clock()/CLOCKS_PER_SEC);
fr(i,0,k) into(i);
// cerr<<"**"<<endl;
// fr(i,0,k+1){
// fr(j,0,k+2) cout<<a[i][j]<<' ';
// cout<<endl;
// }
update();
// fr(i,0,k-1) cout<<x[i]<<endl;
writeln(x[v-1]);
}
signed main(){
// freopen("input.in","r",stdin);
// freopen("output.out","w",stdout);
init();work();
// printf("\nTIME:%.3lf",(double)clock()/CLOCKS_PER_SEC);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 286ms
memory: 8348kb
input:
148 129 48 144 105 13
output:
467058311
result:
ok single line: '467058311'
Test #2:
score: 0
Accepted
time: 3ms
memory: 9888kb
input:
57 48 11 56 9 1
output:
951177245
result:
ok single line: '951177245'
Test #3:
score: 0
Accepted
time: 656ms
memory: 8216kb
input:
121 146 72 117 72 25
output:
284798523
result:
ok single line: '284798523'
Test #4:
score: 0
Accepted
time: 6ms
memory: 7896kb
input:
66 142 11 51 124 4
output:
542285716
result:
ok single line: '542285716'
Test #5:
score: 0
Accepted
time: 821ms
memory: 10024kb
input:
45 127 98 3 31 80
output:
116902187
result:
ok single line: '116902187'
Test #6:
score: 0
Accepted
time: 251ms
memory: 8104kb
input:
125 199 45 51 91 21
output:
715355617
result:
ok single line: '715355617'
Test #7:
score: 0
Accepted
time: 2ms
memory: 9716kb
input:
41 153 6 6 147 2
output:
190519561
result:
ok single line: '190519561'
Test #8:
score: 0
Accepted
time: 455ms
memory: 9960kb
input:
112 108 69 99 29 47
output:
481688971
result:
ok single line: '481688971'
Test #9:
score: 0
Accepted
time: 1189ms
memory: 8480kb
input:
138 99 94 73 43 73
output:
667469005
result:
ok single line: '667469005'
Test #10:
score: 0
Accepted
time: 28ms
memory: 7912kb
input:
143 147 18 24 141 9
output:
763965115
result:
ok single line: '763965115'
Test #11:
score: 0
Accepted
time: 886ms
memory: 8536kb
input:
99 63 97 78 51 66
output:
130195301
result:
ok single line: '130195301'
Test #12:
score: 0
Accepted
time: 3ms
memory: 9672kb
input:
103 23 10 25 7 4
output:
674555733
result:
ok single line: '674555733'
Test #13:
score: 0
Accepted
time: 254ms
memory: 8236kb
input:
137 194 42 125 104 17
output:
416667361
result:
ok single line: '416667361'
Test #14:
score: 0
Accepted
time: 34ms
memory: 9912kb
input:
191 13 37 42 2 21
output:
530754407
result:
ok single line: '530754407'
Test #15:
score: 0
Accepted
time: 172ms
memory: 10008kb
input:
195 33 53 101 29 32
output:
851306824
result:
ok single line: '851306824'
Test #16:
score: 0
Accepted
time: 4ms
memory: 9668kb
input:
84 173 8 70 70 6
output:
25135799
result:
ok single line: '25135799'
Test #17:
score: 0
Accepted
time: 53ms
memory: 9880kb
input:
39 53 49 37 6 9
output:
640044940
result:
ok single line: '640044940'
Test #18:
score: 0
Accepted
time: 584ms
memory: 9960kb
input:
135 129 68 134 86 16
output:
910022919
result:
ok single line: '910022919'
Test #19:
score: 0
Accepted
time: 138ms
memory: 9892kb
input:
62 74 56 28 12 46
output:
774987233
result:
ok single line: '774987233'
Test #20:
score: 0
Accepted
time: 664ms
memory: 8264kb
input:
87 135 81 27 44 58
output:
629485683
result:
ok single line: '629485683'
Test #21:
score: 0
Accepted
time: 295ms
memory: 8040kb
input:
148 199 44 79 81 40
output:
369408819
result:
ok single line: '369408819'
Test #22:
score: 0
Accepted
time: 0ms
memory: 9792kb
input:
18 195 5 17 151 5
output:
198068951
result:
ok single line: '198068951'
Test #23:
score: 0
Accepted
time: 1039ms
memory: 8192kb
input:
200 137 75 67 65 74
output:
864017958
result:
ok single line: '864017958'
Test #24:
score: 0
Accepted
time: 504ms
memory: 8120kb
input:
171 162 56 113 97 30
output:
255341800
result:
ok single line: '255341800'
Test #25:
score: 0
Accepted
time: 22ms
memory: 7948kb
input:
8 134 38 1 93 10
output:
282048962
result:
ok single line: '282048962'
Test #26:
score: 0
Accepted
time: 327ms
memory: 9808kb
input:
13 55 93 3 25 40
output:
852404927
result:
ok single line: '852404927'
Test #27:
score: 0
Accepted
time: 253ms
memory: 9772kb
input:
169 157 42 77 108 39
output:
595819517
result:
ok single line: '595819517'
Test #28:
score: 0
Accepted
time: 745ms
memory: 8236kb
input:
41 199 87 18 82 58
output:
698977796
result:
ok single line: '698977796'
Test #29:
score: 0
Accepted
time: 331ms
memory: 9940kb
input:
190 68 57 188 59 15
output:
46174623
result:
ok single line: '46174623'
Test #30:
score: 0
Accepted
time: 265ms
memory: 8136kb
input:
90 52 71 39 41 23
output:
417181087
result:
ok single line: '417181087'
Test #31:
score: 0
Accepted
time: 645ms
memory: 8204kb
input:
108 76 89 55 40 13
output:
210578964
result:
ok single line: '210578964'
Test #32:
score: 0
Accepted
time: 88ms
memory: 9724kb
input:
166 191 27 102 30 11
output:
365224233
result:
ok single line: '365224233'
Test #33:
score: 0
Accepted
time: 0ms
memory: 7816kb
input:
41 166 4 10 49 2
output:
245797147
result:
ok single line: '245797147'
Test #34:
score: 0
Accepted
time: 690ms
memory: 8200kb
input:
135 128 79 44 16 6
output:
203896980
result:
ok single line: '203896980'
Test #35:
score: 0
Accepted
time: 929ms
memory: 8160kb
input:
101 193 79 43 65 75
output:
27637457
result:
ok single line: '27637457'
Test #36:
score: 0
Accepted
time: 167ms
memory: 8152kb
input:
88 81 53 35 54 47
output:
950708598
result:
ok single line: '950708598'
Test #37:
score: 0
Accepted
time: 17ms
memory: 7788kb
input:
87 40 28 37 8 8
output:
817953396
result:
ok single line: '817953396'
Test #38:
score: 0
Accepted
time: 1506ms
memory: 8284kb
input:
193 136 94 12 94 23
output:
145619900
result:
ok single line: '145619900'
Test #39:
score: 0
Accepted
time: 493ms
memory: 9968kb
input:
90 183 67 8 171 26
output:
899333159
result:
ok single line: '899333159'
Test #40:
score: 0
Accepted
time: 86ms
memory: 7808kb
input:
107 178 32 24 103 12
output:
82019799
result:
ok single line: '82019799'
Test #41:
score: 0
Accepted
time: 158ms
memory: 8008kb
input:
160 23 61 60 17 3
output:
350971684
result:
ok single line: '350971684'
Test #42:
score: 0
Accepted
time: 3ms
memory: 7808kb
input:
100 176 10 54 58 4
output:
978823166
result:
ok single line: '978823166'
Test #43:
score: 0
Accepted
time: 267ms
memory: 9784kb
input:
181 183 42 7 91 41
output:
690262327
result:
ok single line: '690262327'
Test #44:
score: 0
Accepted
time: 189ms
memory: 8008kb
input:
105 131 47 53 68 33
output:
806603020
result:
ok single line: '806603020'
Test #45:
score: 0
Accepted
time: 408ms
memory: 9848kb
input:
51 10 100 1 5 73
output:
341852925
result:
ok single line: '341852925'
Test #46:
score: 0
Accepted
time: 776ms
memory: 9868kb
input:
87 198 73 75 109 72
output:
741170008
result:
ok single line: '741170008'
Test #47:
score: 0
Accepted
time: 0ms
memory: 7964kb
input:
25 158 13 22 1 1
output:
237363061
result:
ok single line: '237363061'
Test #48:
score: 0
Accepted
time: 336ms
memory: 8144kb
input:
64 112 71 28 109 10
output:
350168232
result:
ok single line: '350168232'
Test #49:
score: 0
Accepted
time: 355ms
memory: 7960kb
input:
143 191 52 10 98 10
output:
71885894
result:
ok single line: '71885894'
Test #50:
score: 0
Accepted
time: 45ms
memory: 9856kb
input:
30 130 36 22 85 6
output:
909971212
result:
ok single line: '909971212'
Test #51:
score: 0
Accepted
time: 145ms
memory: 9720kb
input:
154 136 38 34 109 15
output:
655764791
result:
ok single line: '655764791'
Test #52:
score: 0
Accepted
time: 0ms
memory: 9700kb
input:
13 112 7 9 55 1
output:
623849663
result:
ok single line: '623849663'
Test #53:
score: 0
Accepted
time: 200ms
memory: 8020kb
input:
137 103 47 56 77 35
output:
43033659
result:
ok single line: '43033659'
Test #54:
score: 0
Accepted
time: 16ms
memory: 9924kb
input:
40 17 37 11 7 15
output:
803046927
result:
ok single line: '803046927'
Test #55:
score: 0
Accepted
time: 124ms
memory: 10000kb
input:
166 14 58 49 1 26
output:
664593299
result:
ok single line: '664593299'
Test #56:
score: 0
Accepted
time: 15ms
memory: 9872kb
input:
88 195 15 10 120 5
output:
925522664
result:
ok single line: '925522664'
Test #57:
score: -100
Time Limit Exceeded
input:
164 166 96 161 138 32
output:
111053370