QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#379914 | #3082. Ascending Matrix | xlwang | TL | 1783ms | 10044kb | C++14 | 3.5kb | 2024-04-06 19:52:39 | 2024-04-06 19:52:39 |
Judging History
answer
#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(){
rf(i,n+k,1) fr(j,1,m+k){
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){
while(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);
}
swap(value[i],value[j]);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+1) a[val][i]=ksm(val,i);
fr(i,1,k+1) fr(j,1,k) value[i][j]=1ll*K[i][j]*val%mod,add(value[i][j],B[i][j]);
a[val][k+2]=getval();
}
int x[Maxn];
inline void update(){
fr(i,0,k+1){
int id=i;
fr(j,i,k+1) if(a[j][i]>a[id][i]) id=j;
swap(a[id],a[i]);
fr(j,i+1,k+1){
int now=1ll*ksm(a[i][i])*a[j][i]%mod;
fr(l,i,k+2) 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+2],mod-1ll*a[i][j]*x[j]%mod);
x[i]=1ll*a[i][k+2]*ksm(a[i][i])%mod;
}
// fr(i,0,k+1) cout<<i<<' '<<x[i]<<endl;
}
inline void work(){
--k;
fr(i,1,k) fr(j,1,k){
clear();f[n+i][i][0]=1;
dp();
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;
fr(i,0,k+1) into(i);
// fr(i,0,k+1){
// fr(j,0,k+2) cout<<a[i][j]<<' ';
// cout<<endl;
// }
update();
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: 355ms
memory: 10028kb
input:
148 129 48 144 105 13
output:
467058311
result:
ok single line: '467058311'
Test #2:
score: 0
Accepted
time: 0ms
memory: 9700kb
input:
57 48 11 56 9 1
output:
951177245
result:
ok single line: '951177245'
Test #3:
score: 0
Accepted
time: 930ms
memory: 8352kb
input:
121 146 72 117 72 25
output:
284798523
result:
ok single line: '284798523'
Test #4:
score: 0
Accepted
time: 7ms
memory: 9808kb
input:
66 142 11 51 124 4
output:
542285716
result:
ok single line: '542285716'
Test #5:
score: 0
Accepted
time: 1433ms
memory: 10044kb
input:
45 127 98 3 31 80
output:
116902187
result:
ok single line: '116902187'
Test #6:
score: 0
Accepted
time: 324ms
memory: 8108kb
input:
125 199 45 51 91 21
output:
715355617
result:
ok single line: '715355617'
Test #7:
score: 0
Accepted
time: 0ms
memory: 7764kb
input:
41 153 6 6 147 2
output:
190519561
result:
ok single line: '190519561'
Test #8:
score: 0
Accepted
time: 667ms
memory: 8304kb
input:
112 108 69 99 29 47
output:
481688971
result:
ok single line: '481688971'
Test #9:
score: 0
Accepted
time: 1783ms
memory: 9840kb
input:
138 99 94 73 43 73
output:
667469005
result:
ok single line: '667469005'
Test #10:
score: 0
Accepted
time: 32ms
memory: 7932kb
input:
143 147 18 24 141 9
output:
763965115
result:
ok single line: '763965115'
Test #11:
score: -100
Time Limit Exceeded
input:
99 63 97 78 51 66