QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#519096#2568. MountainsRong7AC ✓2ms4216kbC++143.2kb2024-08-14 16:18:362024-08-14 16:18:38

Judging History

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

  • [2024-08-14 16:18:38]
  • 评测
  • 测评结果:AC
  • 用时:2ms
  • 内存:4216kb
  • [2024-08-14 16:18:36]
  • 提交

answer

// Go in my style.
// Not afraid to dark.

#include <bits/stdc++.h>
using namespace std;

clock_t start_time, end_time;
#define GET_START start_time = clock ();
#define GET_END end_time = clock (); fprintf (stderr, "TIME COSSEMED : %0.3lf\n", 1.0 * (end_time - start_time) / CLOCKS_PER_SEC);
#define inline __inline__ __attribute__ ((always_inline))

#define int long long

namespace io {
    int read_pos, read_dt; char read_char;
    inline int read (int &p = read_pos){
        p = 0, read_dt = 1; read_char = getchar ();
        while (! isdigit (read_char)){
            if (read_char == '-')
                read_dt = - 1;
            read_char = getchar ();
        }
        while (isdigit (read_char)){
            p = (p << 1) + (p << 3) + read_char - 48;
            read_char = getchar ();
        }
        return p = p * read_dt;
    }
    int write_sta[65], write_top;
    inline void write (int x){
        if (x < 0)
            putchar ('-'), x = - x;
        write_top = 0;
        do
            write_sta[write_top ++] = x % 10, x /= 10;
        while (x);
        while (write_top)
            putchar (write_sta[-- write_top] + 48);
    }
}

const int N = 100, mod = 1e9 + 7;

int n, m, t;
int inv[N * 2 + 5], inj[N * 2 + 5], jc[N * 2 + 5];

inline int C (int a, int b){
    if (b < 0 || b > a) return 0;
    return jc[a] * inj[b] % mod * inj[a - b] % mod;
}
inline int power (int a, int p){
    static int res; res = 1;
    while (p > 0){
        if (p & 1) res = res * a % mod;
        a = a * a % mod;
        p >>= 1;
    }
    return res;
}

struct matrix {
    int a[N + 5][N + 5];
    inline int* operator [] (const int x){ return a[x]; }
    matrix (int x = 0){
        for (int i = 1;i <= N;++ i)
            for (int j = 1;j <= N;++ j)
                a[i][j] = i == j ? x : 0;
    }
    inline int det (int n){
        static int b[N + 5][N + 5];
        for (int i = 1;i <= n;++ i) for (int j = 1;j <= n;++ j) b[i][j] = a[i][j];
        for (int i = 1;i <= n;++ i){
            if (b[i][i] == 0)
                for (int j = i + 1;j <= n;++ j)
                    if (b[j][i]){
                        for (int k = i;k <= n;++ k)
                            swap (b[i][k], b[j][k]);
                        break;
                    }
            if (b[i][i] == 0) return 0;
            int iv = power (b[i][i], mod - 2);
            for (int j = i + 1;j <= n;++ j)
                if (b[j][i])
                    for (int k = n;k >= i;-- k)
                        b[j][k] = (b[j][k] + mod - b[i][k] * b[j][i] % mod * iv % mod) % mod;
        }
        int ans = 1;
        for (int i = 1;i <= n;++ i) ans = ans * b[i][i] % mod;
        return ans;
    }
} M;

signed main (){
    GET_START

    io::read (n), io::read (m), io::read (t);
    inv[1] = inj[0] = inj[1] = jc[0] = jc[1] = 1;
    for (int i = 2;i <= n + m;++ i){
        inv[i] = inv[i - mod % i] * (mod / i + 1) % mod;
        inj[i] = inj[i - 1] * inv[i] % mod;
        jc[i] = jc[i - 1] * i % mod;
    }
    for (int i = 1;i <= t;++ i)
        for (int j = 1;j <= t;++ j)
            M[i][j] = C (n + m, n + i - j);
    io::write (M.det (t)), putchar ('\n');

    GET_END
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 1 1

output:

2

result:

ok 1 number(s): "2"

Test #2:

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

input:

2 2 2

output:

20

result:

ok 1 number(s): "20"

Test #3:

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

input:

2 3 4

output:

490

result:

ok 1 number(s): "490"

Test #4:

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

input:

1 2 8

output:

45

result:

ok 1 number(s): "45"

Test #5:

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

input:

1 10 2

output:

66

result:

ok 1 number(s): "66"

Test #6:

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

input:

9 5 7

output:

371850968

result:

ok 1 number(s): "371850968"

Test #7:

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

input:

3 3 1

output:

20

result:

ok 1 number(s): "20"

Test #8:

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

input:

7 7 9

output:

166345303

result:

ok 1 number(s): "166345303"

Test #9:

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

input:

25 15 25

output:

850087558

result:

ok 1 number(s): "850087558"

Test #10:

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

input:

45 59 71

output:

659153227

result:

ok 1 number(s): "659153227"

Test #11:

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

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: 4156kb

input:

25 100 32

output:

966287506

result:

ok 1 number(s): "966287506"

Test #14:

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

input:

85 64 40

output:

125679545

result:

ok 1 number(s): "125679545"

Test #15:

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

input:

5 9 94

output:

620471576

result:

ok 1 number(s): "620471576"

Test #16:

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

input:

33 57 40

output:

637315057

result:

ok 1 number(s): "637315057"

Test #17:

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

input:

61 6 97

output:

362472796

result:

ok 1 number(s): "362472796"

Test #18:

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

input:

85 50 51

output:

192099209

result:

ok 1 number(s): "192099209"

Test #19:

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

input:

96 54 59

output:

714762612

result:

ok 1 number(s): "714762612"

Test #20:

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

input:

20 99 12

output:

772155662

result:

ok 1 number(s): "772155662"

Test #21:

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

input:

48 39 62

output:

670046604

result:

ok 1 number(s): "670046604"

Test #22:

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

input:

76 83 16

output:

976820079

result:

ok 1 number(s): "976820079"

Test #23:

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

input:

96 36 61

output:

20854557

result:

ok 1 number(s): "20854557"

Test #24:

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

input:

18 40 77

output:

261684871

result:

ok 1 number(s): "261684871"

Test #25:

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

input:

42 84 26

output:

458573307

result:

ok 1 number(s): "458573307"

Test #26:

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

input:

71 25 80

output:

875902815

result:

ok 1 number(s): "875902815"

Test #27:

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

input:

95 73 26

output:

922299967

result:

ok 1 number(s): "922299967"

Test #28:

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

input:

19 17 83

output:

494148696

result:

ok 1 number(s): "494148696"

Test #29:

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

input:

100 100 100

output:

192912055

result:

ok 1 number(s): "192912055"

Test #30:

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

input:

100 98 99

output:

412293529

result:

ok 1 number(s): "412293529"