QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#810272	#79. Fabricating Sculptures	SGColin	AC ✓	112ms	145660kb	C++20	1.2kb	2024-12-11 20:50:14	2024-12-11 20:50:31

Judging History

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

[2024-12-11 20:50:31]
评测

测评结果：AC
用时：112ms
内存：145660kb

查看

[2024-12-11 20:50:14]
提交

answer

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

int rd() {
    int x = 0; 
    bool f = 0; 
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define fr        first
#define sc        second
#define mp        make_pair
#define pb        push_back
#define pii       pair<int, int>
#define all(s)    (s).begin(), (s).end()
#define lowbit(x) ((x) & -(x))

#define N   5007
#define mod 1000000007

int f[N][N], sum[N][N], sumk[N][N];

int main() {
    int m = rd(), n = rd();
    f[m][m] = 1;
    for (int j = m; j; --j) {
        sum[m][j] = (sum[m][j + 1] + f[m][j]) % mod;
        sumk[m][j] = (sumk[m][j + 1] + 1ll * j * f[m][j]) % mod;    
    }
    for (int use = m + 1; use <= n; ++use) {
        for (int j = min(m, use); j; --j) {
            f[use][j] = (sumk[use - j][j] + 1ll * sum[use - j][j] * (1 - j + mod)) % mod;
            sum[use][j] = (sum[use][j + 1] + f[use][j]) % mod;
            sumk[use][j] = (sumk[use][j + 1] + 1ll * j * f[use][j]) % mod;
        }
    }
    printf("%d\n", sum[n][1]);
    return 0;
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 6024kb

input:

3 6

output:

result:

ok single line: '8'

Test #2:

score: 0

Accepted

time: 1ms

memory: 5872kb

input:

2 3

output:

result:

ok single line: '2'

Test #3:

score: 0

Accepted

time: 1ms

memory: 5852kb

input:

3 5

output:

result:

ok single line: '5'

Test #4:

score: 0

Accepted

time: 1ms

memory: 5888kb

input:

4 6

output:

result:

ok single line: '7'

Test #5:

score: 0

Accepted

time: 0ms

memory: 5944kb

input:

5 7

output:

result:

ok single line: '9'

Test #6:

score: 0

Accepted

time: 1ms

memory: 5828kb

input:

6 8

output:

result:

ok single line: '11'

Test #7:

score: 0

Accepted

time: 1ms

memory: 5912kb

input:

6 9

output:

result:

ok single line: '20'

Test #8:

score: 0

Accepted

time: 0ms

memory: 5904kb

input:

4 10

output:

result:

ok single line: '42'

Test #9:

score: 0

Accepted

time: 100ms

memory: 122588kb

input:

2505 5000

output:

419207368

result:

ok single line: '419207368'

Test #10:

score: 0

Accepted

time: 77ms

memory: 122708kb

input:

2504 5000

output:

496364578

result:

ok single line: '496364578'

Test #11:

score: 0

Accepted

time: 71ms

memory: 122680kb

input:

2500 5000

output:

806080506

result:

ok single line: '806080506'

Test #12:

score: 0

Accepted

time: 1ms

memory: 5972kb

input:

3 7

output:

result:

ok single line: '12'

Test #13:

score: 0

Accepted

time: 78ms

memory: 121908kb

input:

2499 5000

output:

306386138

result:

ok single line: '306386138'

Test #14:

score: 0

Accepted

time: 75ms

memory: 122168kb

input:

2498 5000

output:

788681364

result:

ok single line: '788681364'

Test #15:

score: 0

Accepted

time: 90ms

memory: 122908kb

input:

2497 5000

output:

812170482

result:

ok single line: '812170482'

Test #16:

score: 0

Accepted

time: 112ms

memory: 123064kb

input:

2496 5000

output:

762896457

result:

ok single line: '762896457'

Test #17:

score: 0

Accepted

time: 84ms

memory: 122504kb

input:

2495 5000

output:

110253511

result:

ok single line: '110253511'

Test #18:

score: 0

Accepted

time: 24ms

memory: 56464kb

input:

4123 5000

output:

108131593

result:

ok single line: '108131593'

Test #19:

score: 0

Accepted

time: 44ms

memory: 71960kb

input:

3841 5000

output:

521097090

result:

ok single line: '521097090'

Test #20:

score: 0

Accepted

time: 86ms

memory: 145660kb

input:

1042 5000

output:

193901029

result:

ok single line: '193901029'

Test #21:

score: 0

Accepted

time: 43ms

memory: 89036kb

input:

2109 4000

output:

811834927

result:

ok single line: '811834927'

Test #22:

score: 0

Accepted

time: 32ms

memory: 66792kb

input:

1417 3000

output:

46698841

result:

ok single line: '46698841'

Test #23:

score: 0

Accepted

time: 96ms

memory: 130360kb

input:

2183 5000

output:

373919320

result:

ok single line: '373919320'

Test #24:

score: 0

Accepted

time: 7ms

memory: 42244kb

input:

999 2000

output:

70869124

result:

ok single line: '70869124'

Test #25:

score: 0

Accepted

time: 8ms

memory: 19468kb

input:

566 1000

output:

405298962

result:

ok single line: '405298962'

Test #26:

score: 0

Accepted

time: 4ms

memory: 22196kb

input:

487 1000

output:

456099947

result:

ok single line: '456099947'

Test #27:

score: 0

Accepted

time: 1ms

memory: 6072kb

input:

27 50

output:

result:

ok single line: '569190'

Test #28:

score: 0

Accepted

time: 1ms

memory: 6084kb

input:

33 60

output:

result:

ok single line: '2557608'

Test #29:

score: 0

Accepted

time: 0ms

memory: 7896kb

input:

66 70

output:

result:

ok single line: '516'

Test #30:

score: 0

Accepted

time: 1ms

memory: 8272kb

input:

48 80

output:

17766031

result:

ok single line: '17766031'

Test #31:

score: 0

Accepted

time: 1ms

memory: 6168kb

input:

55 90

output:

47940391

result:

ok single line: '47940391'

Test #32:

score: 0

Accepted

time: 1ms

memory: 8164kb

input:

72 100

output:

result:

ok single line: '9265107'

Test #33:

score: 0

Accepted

time: 0ms

memory: 8716kb

input:

111 200

output:

991289685

result:

ok single line: '991289685'

Test #34:

score: 0

Accepted

time: 86ms

memory: 122760kb

input:

2503 5000

output:

845880902

result:

ok single line: '845880902'

Test #35:

score: 0

Accepted

time: 2ms

memory: 8824kb

input:

198 300

output:

118013787

result:

ok single line: '118013787'

Test #36:

score: 0

Accepted

time: 0ms

memory: 6408kb

input:

351 400

output:

911070728

result:

ok single line: '911070728'

Test #37:

score: 0

Accepted

time: 2ms

memory: 17976kb

input:

22 500

output:

614964048

result:

ok single line: '614964048'

Test #38:

score: 0

Accepted

time: 4ms

memory: 14840kb

input:

200 500

output:

97398918

result:

ok single line: '97398918'

Test #39:

score: 0

Accepted

time: 0ms

memory: 8404kb

input:

455 500

output:

497174488

result:

ok single line: '497174488'

Test #40:

score: 0

Accepted

time: 4ms

memory: 15184kb

input:

300 600

output:

704360407

result:

ok single line: '704360407'

Test #41:

score: 0

Accepted

time: 0ms

memory: 11728kb

input:

555 700

output:

392947597

result:

ok single line: '392947597'

Test #42:

score: 0

Accepted

time: 1ms

memory: 6032kb

input:

790 800

output:

result:

ok single line: '164231'

Test #43:

score: 0

Accepted

time: 4ms

memory: 22384kb

input:

300 900

output:

281421689

result:

ok single line: '281421689'

Test #44:

score: 0

Accepted

time: 0ms

memory: 34332kb

input:

33 1000

output:

936696284

result:

ok single line: '936696284'

Test #45:

score: 0

Accepted

time: 88ms

memory: 121728kb

input:

2502 5000

output:

595029502

result:

ok single line: '595029502'

Test #46:

score: 0

Accepted

time: 90ms

memory: 120968kb

input:

2501 5000

output:

849299043

result:

ok single line: '849299043'

Test #47:

score: 0

Accepted

time: 1ms

memory: 5876kb

input:

1 1

output:

result:

ok single line: '1'

Test #48:

score: 0

Accepted

time: 1ms

memory: 5828kb

input:

1 2

output:

result:

ok single line: '1'

Test #49:

score: 0

Accepted

time: 1ms

memory: 5884kb

input:

2 2

output:

result:

ok single line: '1'