QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#291153#2153. HILOMoRanSky100 ✓69ms3968kbC++231.9kb2023-12-26 05:06:592023-12-26 05:07:00

Judging History

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

  • [2023-12-26 05:07:00]
  • 评测
  • 测评结果:100
  • 用时:69ms
  • 内存:3968kb
  • [2023-12-26 05:06:59]
  • 提交

answer

// Skyqwq
#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 5e3 + 5, P = 1e9 + 7;

int n, x, fact[N], infact[N], f[N], g[N];

int inline power(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = (LL)res * a % P;
        a = (LL)a * a % P;
        b >>= 1;
    }
    return res;
}

void inline add(int &x, int y) {
    x += y;
    if (x >= P) x -= P;
}

void inline factPrework(int n) {
    fact[0] = infact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = (LL)fact[i - 1] * i % P;
    infact[n] = power(fact[n], P - 2);
    for (int i = n - 1; i; i--) infact[i] = infact[i + 1] * (i + 1ll) % P;
}

int inline C(int a, int b) {
    if (a < b || a < 0 || b < 0) return 0;
    return (LL)fact[a] * infact[b] % P * infact[a - b] % P;
}

int inv2 = (P + 1) / 2;

int main() {
    factPrework(5e3 + 1);
    read(n), read(x);
    int ans = 0;
    for (int i = 0; i < n - x; i++) {
        for (int j = 0; j < x; j++) {
            if (!j) add(ans, 1ll * fact[i + 1] * C(n - x, i + 1) % P * C(x, j + 1) % P * fact[n - i - j - 2] % P);
            else {
                int gx = 1ll * fact[i + j + 1] * inv2 % P;
                add(ans, 1ll * gx * C(n - x, i + 1) % P * C(x, j + 1) % P * fact[n - i - j - 2] % P);
            }
        }
    }

    printf("%d\n", ans);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 2

output:

17

result:

ok 1 number(s): "17"

Test #2:

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

input:

60 10

output:

508859913

result:

ok 1 number(s): "508859913"

Test #3:

score: 3.84615
Accepted
time: 0ms
memory: 3772kb

input:

36 2

output:

653172943

result:

ok 1 number(s): "653172943"

Test #4:

score: 3.84615
Accepted
time: 0ms
memory: 3868kb

input:

38 12

output:

877759561

result:

ok 1 number(s): "877759561"

Test #5:

score: 3.84615
Accepted
time: 0ms
memory: 3968kb

input:

40 22

output:

587738552

result:

ok 1 number(s): "587738552"

Test #6:

score: 3.84615
Accepted
time: 0ms
memory: 3824kb

input:

42 9

output:

142300060

result:

ok 1 number(s): "142300060"

Test #7:

score: 3.84615
Accepted
time: 0ms
memory: 3784kb

input:

44 42

output:

194449602

result:

ok 1 number(s): "194449602"

Test #8:

score: 3.84615
Accepted
time: 0ms
memory: 3868kb

input:

46 41

output:

996298696

result:

ok 1 number(s): "996298696"

Test #9:

score: 3.84615
Accepted
time: 0ms
memory: 3884kb

input:

48 16

output:

933315069

result:

ok 1 number(s): "933315069"

Test #10:

score: 3.84615
Accepted
time: 0ms
memory: 3804kb

input:

50 1

output:

592235889

result:

ok 1 number(s): "592235889"

Test #11:

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

input:

106 25

output:

370147128

result:

ok 1 number(s): "370147128"

Test #12:

score: 3.84615
Accepted
time: 0ms
memory: 3772kb

input:

162 125

output:

588210522

result:

ok 1 number(s): "588210522"

Test #13:

score: 3.84615
Accepted
time: 1ms
memory: 3784kb

input:

218 196

output:

722904144

result:

ok 1 number(s): "722904144"

Test #14:

score: 3.84615
Accepted
time: 1ms
memory: 3836kb

input:

275 77

output:

201201377

result:

ok 1 number(s): "201201377"

Test #15:

score: 3.84615
Accepted
time: 1ms
memory: 3844kb

input:

331 195

output:

105599195

result:

ok 1 number(s): "105599195"

Test #16:

score: 3.84615
Accepted
time: 1ms
memory: 3788kb

input:

387 160

output:

51654417

result:

ok 1 number(s): "51654417"

Test #17:

score: 3.84615
Accepted
time: 1ms
memory: 3876kb

input:

443 407

output:

973597938

result:

ok 1 number(s): "973597938"

Test #18:

score: 3.84615
Accepted
time: 1ms
memory: 3808kb

input:

500 196

output:

279036314

result:

ok 1 number(s): "279036314"

Test #19:

score: 3.84615
Accepted
time: 69ms
memory: 3792kb

input:

4944 2238

output:

373098474

result:

ok 1 number(s): "373098474"

Test #20:

score: 3.84615
Accepted
time: 51ms
memory: 3864kb

input:

4952 3750

output:

127862445

result:

ok 1 number(s): "127862445"

Test #21:

score: 3.84615
Accepted
time: 66ms
memory: 3872kb

input:

4960 2465

output:

524400159

result:

ok 1 number(s): "524400159"

Test #22:

score: 3.84615
Accepted
time: 67ms
memory: 3876kb

input:

4968 3013

output:

429923833

result:

ok 1 number(s): "429923833"

Test #23:

score: 3.84615
Accepted
time: 68ms
memory: 3844kb

input:

4976 2108

output:

909616241

result:

ok 1 number(s): "909616241"

Test #24:

score: 3.84615
Accepted
time: 63ms
memory: 3908kb

input:

4984 1656

output:

572267695

result:

ok 1 number(s): "572267695"

Test #25:

score: 3.84615
Accepted
time: 54ms
memory: 3960kb

input:

4992 3695

output:

824711289

result:

ok 1 number(s): "824711289"

Test #26:

score: 3.84615
Accepted
time: 12ms
memory: 3792kb

input:

5000 207

output:

765133070

result:

ok 1 number(s): "765133070"