QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#379926#3082. Ascending MatrixxlwangTL 1665ms10072kbC++145.7kb2024-04-06 19:59:082024-04-06 19:59:09

Judging History

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

  • [2024-04-06 19:59:09]
  • 评测
  • 测评结果:TL
  • 用时:1665ms
  • 内存:10072kb
  • [2024-04-06 19:59:08]
  • 提交

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(){
    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) 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;
    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) 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: 341ms
memory: 10072kb

input:

148 129 48 144 105 13

output:

467058311

result:

ok single line: '467058311'

Test #2:

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

input:

57 48 11 56 9 1

output:

951177245

result:

ok single line: '951177245'

Test #3:

score: 0
Accepted
time: 870ms
memory: 9840kb

input:

121 146 72 117 72 25

output:

284798523

result:

ok single line: '284798523'

Test #4:

score: 0
Accepted
time: 6ms
memory: 7968kb

input:

66 142 11 51 124 4

output:

542285716

result:

ok single line: '542285716'

Test #5:

score: 0
Accepted
time: 1308ms
memory: 9952kb

input:

45 127 98 3 31 80

output:

116902187

result:

ok single line: '116902187'

Test #6:

score: 0
Accepted
time: 301ms
memory: 9844kb

input:

125 199 45 51 91 21

output:

715355617

result:

ok single line: '715355617'

Test #7:

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

input:

41 153 6 6 147 2

output:

190519561

result:

ok single line: '190519561'

Test #8:

score: 0
Accepted
time: 622ms
memory: 8348kb

input:

112 108 69 99 29 47

output:

481688971

result:

ok single line: '481688971'

Test #9:

score: 0
Accepted
time: 1665ms
memory: 9840kb

input:

138 99 94 73 43 73

output:

667469005

result:

ok single line: '667469005'

Test #10:

score: 0
Accepted
time: 27ms
memory: 9852kb

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

output:


result: