QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#503552#2573. Two PermutationsFRZ_29AC ✓487ms21968kbC++141.5kb2024-08-03 19:56:392024-08-03 19:56:40

Judging History

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

  • [2024-08-03 19:56:40]
  • 评测
  • 测评结果:AC
  • 用时:487ms
  • 内存:21968kb
  • [2024-08-03 19:56:39]
  • 提交

answer

#include <iostream>
#include <cstring>
#include <cstdio>
typedef long long LL;

using namespace std;

inline int RD() {
    int x = 0, f = 1;
    char ch = getchar();

    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }

    while (ch >= '0' && ch <= '9')
        x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x * f;
}

const int N = 105;
const LL mod = 1e9 + 7;

#define MOD(x) (((x) + mod) % mod)
#define LF(i, __l, __r) for (int i = __l; i <= __r; i++)
#define RF(i, __r, __l) for (int i = __r; i >= __l; i--)

int n, k;
LL f[2][N][N * N]; // 第 1 维为处理到了第 i 个数,第 2 维已经处理好了 j 对数,第 3 维为现在数的和。
// 表示方案数

int main() {
    n = RD(), k = RD();
    f[0][0][0] = 1;

    LF(i, 1, n) {
        memset(f[i & 1], 0, sizeof(f[i & 1]));
        LF(j, 0, i - 1) {
            LF(l, 0, k) {
                LL x = j, y = (i - 1) - j, z = n - x - y * 2;
                LL &a = f[i & 1][j + 1][l + i],
                    &b = f[i & 1][j + 2][l + 2 * i], 
                    &c = f[i & 1][j][l],
                    d = f[(i - 1) & 1][j][l];
                a = MOD(MOD(d * z) + a);
                a = MOD(MOD(d * MOD(y * MOD(2 * z))) + a);
                b = MOD(MOD(d * y) * y + b);
                c = MOD(MOD(d * z) * (z - 1) + c);
            }
        }
    }

    printf("%lld", f[n & 1][n][k]);
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 21876kb

input:

2 4

output:

2

result:

ok 1 number(s): "2"

Test #2:

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

input:

3 7

output:

12

result:

ok 1 number(s): "12"

Test #3:

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

input:

4 10

output:

24

result:

ok 1 number(s): "24"

Test #4:

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

input:

4 14

output:

96

result:

ok 1 number(s): "96"

Test #5:

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

input:

5 10

output:

0

result:

ok 1 number(s): "0"

Test #6:

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

input:

5 15

output:

120

result:

ok 1 number(s): "120"

Test #7:

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

input:

5 21

output:

2400

result:

ok 1 number(s): "2400"

Test #8:

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

input:

6 21

output:

720

result:

ok 1 number(s): "720"

Test #9:

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

input:

6 30

output:

25920

result:

ok 1 number(s): "25920"

Test #10:

score: 0
Accepted
time: 5ms
memory: 21808kb

input:

6 27

output:

106560

result:

ok 1 number(s): "106560"

Test #11:

score: 0
Accepted
time: 5ms
memory: 21884kb

input:

20 300

output:

644873710

result:

ok 1 number(s): "644873710"

Test #12:

score: 0
Accepted
time: 7ms
memory: 21820kb

input:

20 139

output:

0

result:

ok 1 number(s): "0"

Test #13:

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

input:

30 470

output:

491424690

result:

ok 1 number(s): "491424690"

Test #14:

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

input:

30 500

output:

8436035

result:

ok 1 number(s): "8436035"

Test #15:

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

input:

40 1000

output:

617159088

result:

ok 1 number(s): "617159088"

Test #16:

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

input:

40 900

output:

729805907

result:

ok 1 number(s): "729805907"

Test #17:

score: 0
Accepted
time: 48ms
memory: 21896kb

input:

60 1830

output:

16340084

result:

ok 1 number(s): "16340084"

Test #18:

score: 0
Accepted
time: 56ms
memory: 21832kb

input:

60 2000

output:

832198921

result:

ok 1 number(s): "832198921"

Test #19:

score: 0
Accepted
time: 266ms
memory: 21804kb

input:

100 5050

output:

437918130

result:

ok 1 number(s): "437918130"

Test #20:

score: 0
Accepted
time: 62ms
memory: 21900kb

input:

100 700

output:

0

result:

ok 1 number(s): "0"

Test #21:

score: 0
Accepted
time: 487ms
memory: 21876kb

input:

100 10000

output:

0

result:

ok 1 number(s): "0"