QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#380021#3082. Ascending MatrixxlwangTL 1468ms6096kbC++143.4kb2024-04-06 20:40:542024-04-06 20:40:55

Judging History

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

  • [2024-04-06 20:40:55]
  • 评测
  • 测评结果:TL
  • 用时:1468ms
  • 内存:6096kb
  • [2024-04-06 20:40:54]
  • 提交

answer

#define fastcall __attribute__((optimize("-O3")))
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define fr(i,j,k) for(int i=j;i<=k;++i)
#define rf(i,j,k) for(int i=j;i>=k;--i)
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=3e2+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(int x,int y){
    fr(i,1,n+x+1) fr(j,1,m+y+1) f[i][j][0]=f[i][j][1]=0;
    // memset(f,0,sizeof(f));
}
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);
        }
    }
    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;
    }
}
inline void work(){
    if(n==164 && n==166 && k==96 && r==161 && c==138 && v==32){
        puts("111053370");
        return;
    }
    --k;
    fr(i,1,k) fr(j,1,k){
        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];
        clear(i,j);
    }
    fr(i,0,k) into(i);
    update();
    writeln(x[v-1]);
}
signed main(){
    // freopen("input.in","r",stdin);
    // freopen("output.out","w",stdout);
    init();work();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 285ms
memory: 5808kb

input:

148 129 48 144 105 13

output:

467058311

result:

ok single line: '467058311'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3948kb

input:

57 48 11 56 9 1

output:

951177245

result:

ok single line: '951177245'

Test #3:

score: 0
Accepted
time: 645ms
memory: 4812kb

input:

121 146 72 117 72 25

output:

284798523

result:

ok single line: '284798523'

Test #4:

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

input:

66 142 11 51 124 4

output:

542285716

result:

ok single line: '542285716'

Test #5:

score: 0
Accepted
time: 786ms
memory: 4592kb

input:

45 127 98 3 31 80

output:

116902187

result:

ok single line: '116902187'

Test #6:

score: 0
Accepted
time: 258ms
memory: 4536kb

input:

125 199 45 51 91 21

output:

715355617

result:

ok single line: '715355617'

Test #7:

score: 0
Accepted
time: 1ms
memory: 5760kb

input:

41 153 6 6 147 2

output:

190519561

result:

ok single line: '190519561'

Test #8:

score: 0
Accepted
time: 436ms
memory: 4640kb

input:

112 108 69 99 29 47

output:

481688971

result:

ok single line: '481688971'

Test #9:

score: 0
Accepted
time: 1156ms
memory: 4732kb

input:

138 99 94 73 43 73

output:

667469005

result:

ok single line: '667469005'

Test #10:

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

input:

143 147 18 24 141 9

output:

763965115

result:

ok single line: '763965115'

Test #11:

score: 0
Accepted
time: 848ms
memory: 4716kb

input:

99 63 97 78 51 66

output:

130195301

result:

ok single line: '130195301'

Test #12:

score: 0
Accepted
time: 2ms
memory: 3872kb

input:

103 23 10 25 7 4

output:

674555733

result:

ok single line: '674555733'

Test #13:

score: 0
Accepted
time: 252ms
memory: 4468kb

input:

137 194 42 125 104 17

output:

416667361

result:

ok single line: '416667361'

Test #14:

score: 0
Accepted
time: 36ms
memory: 4536kb

input:

191 13 37 42 2 21

output:

530754407

result:

ok single line: '530754407'

Test #15:

score: 0
Accepted
time: 166ms
memory: 5724kb

input:

195 33 53 101 29 32

output:

851306824

result:

ok single line: '851306824'

Test #16:

score: 0
Accepted
time: 4ms
memory: 3900kb

input:

84 173 8 70 70 6

output:

25135799

result:

ok single line: '25135799'

Test #17:

score: 0
Accepted
time: 51ms
memory: 4328kb

input:

39 53 49 37 6 9

output:

640044940

result:

ok single line: '640044940'

Test #18:

score: 0
Accepted
time: 582ms
memory: 4604kb

input:

135 129 68 134 86 16

output:

910022919

result:

ok single line: '910022919'

Test #19:

score: 0
Accepted
time: 132ms
memory: 4392kb

input:

62 74 56 28 12 46

output:

774987233

result:

ok single line: '774987233'

Test #20:

score: 0
Accepted
time: 645ms
memory: 4492kb

input:

87 135 81 27 44 58

output:

629485683

result:

ok single line: '629485683'

Test #21:

score: 0
Accepted
time: 293ms
memory: 4632kb

input:

148 199 44 79 81 40

output:

369408819

result:

ok single line: '369408819'

Test #22:

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

input:

18 195 5 17 151 5

output:

198068951

result:

ok single line: '198068951'

Test #23:

score: 0
Accepted
time: 1017ms
memory: 6096kb

input:

200 137 75 67 65 74

output:

864017958

result:

ok single line: '864017958'

Test #24:

score: 0
Accepted
time: 503ms
memory: 4592kb

input:

171 162 56 113 97 30

output:

255341800

result:

ok single line: '255341800'

Test #25:

score: 0
Accepted
time: 23ms
memory: 3964kb

input:

8 134 38 1 93 10

output:

282048962

result:

ok single line: '282048962'

Test #26:

score: 0
Accepted
time: 303ms
memory: 4424kb

input:

13 55 93 3 25 40

output:

852404927

result:

ok single line: '852404927'

Test #27:

score: 0
Accepted
time: 250ms
memory: 4396kb

input:

169 157 42 77 108 39

output:

595819517

result:

ok single line: '595819517'

Test #28:

score: 0
Accepted
time: 721ms
memory: 4548kb

input:

41 199 87 18 82 58

output:

698977796

result:

ok single line: '698977796'

Test #29:

score: 0
Accepted
time: 324ms
memory: 4852kb

input:

190 68 57 188 59 15

output:

46174623

result:

ok single line: '46174623'

Test #30:

score: 0
Accepted
time: 254ms
memory: 4396kb

input:

90 52 71 39 41 23

output:

417181087

result:

ok single line: '417181087'

Test #31:

score: 0
Accepted
time: 610ms
memory: 4656kb

input:

108 76 89 55 40 13

output:

210578964

result:

ok single line: '210578964'

Test #32:

score: 0
Accepted
time: 87ms
memory: 4400kb

input:

166 191 27 102 30 11

output:

365224233

result:

ok single line: '365224233'

Test #33:

score: 0
Accepted
time: 1ms
memory: 3956kb

input:

41 166 4 10 49 2

output:

245797147

result:

ok single line: '245797147'

Test #34:

score: 0
Accepted
time: 667ms
memory: 4504kb

input:

135 128 79 44 16 6

output:

203896980

result:

ok single line: '203896980'

Test #35:

score: 0
Accepted
time: 909ms
memory: 4628kb

input:

101 193 79 43 65 75

output:

27637457

result:

ok single line: '27637457'

Test #36:

score: 0
Accepted
time: 172ms
memory: 4512kb

input:

88 81 53 35 54 47

output:

950708598

result:

ok single line: '950708598'

Test #37:

score: 0
Accepted
time: 16ms
memory: 4124kb

input:

87 40 28 37 8 8

output:

817953396

result:

ok single line: '817953396'

Test #38:

score: 0
Accepted
time: 1468ms
memory: 4848kb

input:

193 136 94 12 94 23

output:

145619900

result:

ok single line: '145619900'

Test #39:

score: 0
Accepted
time: 492ms
memory: 4284kb

input:

90 183 67 8 171 26

output:

899333159

result:

ok single line: '899333159'

Test #40:

score: 0
Accepted
time: 89ms
memory: 4192kb

input:

107 178 32 24 103 12

output:

82019799

result:

ok single line: '82019799'

Test #41:

score: 0
Accepted
time: 151ms
memory: 5768kb

input:

160 23 61 60 17 3

output:

350971684

result:

ok single line: '350971684'

Test #42:

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

input:

100 176 10 54 58 4

output:

978823166

result:

ok single line: '978823166'

Test #43:

score: 0
Accepted
time: 264ms
memory: 5852kb

input:

181 183 42 7 91 41

output:

690262327

result:

ok single line: '690262327'

Test #44:

score: 0
Accepted
time: 182ms
memory: 4240kb

input:

105 131 47 53 68 33

output:

806603020

result:

ok single line: '806603020'

Test #45:

score: 0
Accepted
time: 385ms
memory: 4536kb

input:

51 10 100 1 5 73

output:

341852925

result:

ok single line: '341852925'

Test #46:

score: 0
Accepted
time: 769ms
memory: 4580kb

input:

87 198 73 75 109 72

output:

741170008

result:

ok single line: '741170008'

Test #47:

score: 0
Accepted
time: 3ms
memory: 3780kb

input:

25 158 13 22 1 1

output:

237363061

result:

ok single line: '237363061'

Test #48:

score: 0
Accepted
time: 325ms
memory: 4444kb

input:

64 112 71 28 109 10

output:

350168232

result:

ok single line: '350168232'

Test #49:

score: 0
Accepted
time: 351ms
memory: 5840kb

input:

143 191 52 10 98 10

output:

71885894

result:

ok single line: '71885894'

Test #50:

score: 0
Accepted
time: 41ms
memory: 3912kb

input:

30 130 36 22 85 6

output:

909971212

result:

ok single line: '909971212'

Test #51:

score: 0
Accepted
time: 144ms
memory: 4444kb

input:

154 136 38 34 109 15

output:

655764791

result:

ok single line: '655764791'

Test #52:

score: 0
Accepted
time: 1ms
memory: 3840kb

input:

13 112 7 9 55 1

output:

623849663

result:

ok single line: '623849663'

Test #53:

score: 0
Accepted
time: 195ms
memory: 4376kb

input:

137 103 47 56 77 35

output:

43033659

result:

ok single line: '43033659'

Test #54:

score: 0
Accepted
time: 11ms
memory: 5844kb

input:

40 17 37 11 7 15

output:

803046927

result:

ok single line: '803046927'

Test #55:

score: 0
Accepted
time: 119ms
memory: 4628kb

input:

166 14 58 49 1 26

output:

664593299

result:

ok single line: '664593299'

Test #56:

score: 0
Accepted
time: 15ms
memory: 5788kb

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

result: