QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#476655#2568. MountainsDEMONKILLERAC ✓1ms4188kbC++231.3kb2024-07-13 20:37:312024-07-13 20:37:32

Judging History

This is the latest submission verdict.

  • [2024-07-13 20:37:32]
  • Judged
  • Verdict: AC
  • Time: 1ms
  • Memory: 4188kb
  • [2024-07-13 20:37:31]
  • Submitted

answer

#include<bits/stdc++.h>
#define N 310
#define mod 1000000007
using namespace std;
int n,m,K;
long long res=1,fac[N],inv[N],g[N][N];
long long qpow(long long a,int b){
    long long Res=1;
    while(b){
        if(b&1)Res=Res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return Res;
}
long long c(int a,int b){
    return fac[a]*inv[b]%mod*inv[a-b]%mod;
}
int main(){
    scanf("%d%d%d",&n,&m,&K);
    fac[0]=fac[1]=1;
    for(int i=2;i<=N-10;i++)fac[i]=fac[i-1]*i%mod;
    inv[N-10]=qpow(fac[N-10],mod-2);
    for(int i=N-11;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
    for(int i=1;i<=K;i++)
        for(int j=1;j<=K;j++)
            g[i][j]=c(n+m,m+j-i);
    for(int i=1;i<=K;i++){
        int v=K+1;
        for(int j=i;j<=K;j++){
            if(g[j][i]){
                v=j;
                break;
            }
        }
        if(v==K+1){
            res=0;
            break;
        }
        if(v!=i){
            swap(g[v],g[i]);
            res=mod-res;
        }
        int inv=qpow(g[i][i],mod-2);
        for(int j=i+1;j<=K;j++){
            long long mul=g[j][i]*inv%mod;
            for(int k=i;k<=K;k++)
                g[j][k]=(g[j][k]-g[i][k]*mul%mod+mod)%mod;
        }
        res=res*g[i][i]%mod;
    }
    printf("%lld",res);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3808kb

input:

1 1 1

output:

2

result:

ok 1 number(s): "2"

Test #2:

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

input:

2 2 2

output:

20

result:

ok 1 number(s): "20"

Test #3:

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

input:

2 3 4

output:

490

result:

ok 1 number(s): "490"

Test #4:

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

input:

1 2 8

output:

45

result:

ok 1 number(s): "45"

Test #5:

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

input:

1 10 2

output:

66

result:

ok 1 number(s): "66"

Test #6:

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

input:

9 5 7

output:

371850968

result:

ok 1 number(s): "371850968"

Test #7:

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

input:

3 3 1

output:

20

result:

ok 1 number(s): "20"

Test #8:

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

input:

7 7 9

output:

166345303

result:

ok 1 number(s): "166345303"

Test #9:

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

input:

25 15 25

output:

850087558

result:

ok 1 number(s): "850087558"

Test #10:

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

input:

45 59 71

output:

659153227

result:

ok 1 number(s): "659153227"

Test #11:

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

input:

73 3 25

output:

683124269

result:

ok 1 number(s): "683124269"

Test #12:

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

input:

1 48 78

output:

446896916

result:

ok 1 number(s): "446896916"

Test #13:

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

input:

25 100 32

output:

966287506

result:

ok 1 number(s): "966287506"

Test #14:

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

input:

85 64 40

output:

125679545

result:

ok 1 number(s): "125679545"

Test #15:

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

input:

5 9 94

output:

620471576

result:

ok 1 number(s): "620471576"

Test #16:

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

input:

33 57 40

output:

637315057

result:

ok 1 number(s): "637315057"

Test #17:

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

input:

61 6 97

output:

362472796

result:

ok 1 number(s): "362472796"

Test #18:

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

input:

85 50 51

output:

192099209

result:

ok 1 number(s): "192099209"

Test #19:

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

input:

96 54 59

output:

714762612

result:

ok 1 number(s): "714762612"

Test #20:

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

input:

20 99 12

output:

772155662

result:

ok 1 number(s): "772155662"

Test #21:

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

input:

48 39 62

output:

670046604

result:

ok 1 number(s): "670046604"

Test #22:

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

input:

76 83 16

output:

976820079

result:

ok 1 number(s): "976820079"

Test #23:

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

input:

96 36 61

output:

20854557

result:

ok 1 number(s): "20854557"

Test #24:

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

input:

18 40 77

output:

261684871

result:

ok 1 number(s): "261684871"

Test #25:

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

input:

42 84 26

output:

458573307

result:

ok 1 number(s): "458573307"

Test #26:

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

input:

71 25 80

output:

875902815

result:

ok 1 number(s): "875902815"

Test #27:

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

input:

95 73 26

output:

922299967

result:

ok 1 number(s): "922299967"

Test #28:

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

input:

19 17 83

output:

494148696

result:

ok 1 number(s): "494148696"

Test #29:

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

input:

100 100 100

output:

192912055

result:

ok 1 number(s): "192912055"

Test #30:

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

input:

100 98 99

output:

412293529

result:

ok 1 number(s): "412293529"