QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#261930#1651. Modulo Permutationsucup-team133#AC ✓88ms11000kbC++17946b2023-11-23 13:42:222023-11-23 13:42:22

Judging History

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

  • [2023-11-23 13:42:22]
  • 评测
  • 测评结果：AC
  • 用时：88ms
  • 内存：11000kb
查看
  • [2023-11-23 13:42:22]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const long long mod = (int) 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    if (n <= 2) {
        cout << n << '\n';
        return 0;
    }
    vector<long long> dp(n + 10);
    dp[3] = 1;
    for (int i = 3; i < n; i++) {
        for (int j = (i - 1); j <= n; j += i - 1) {
            for (int k = 0; k <= 2; k++) {
                if (k == 2 && i == 3) {
                    continue;
                } else if (j + k <= i) {
                    continue;
                }
                dp[j + k] = (dp[j + k] + dp[i]) % mod;
            }
        }
//        for (int j = 0; j <= n; j++) {
//            cerr << dp[j] << " \n"[j == n];
//        }
    }
    long long ans = 0;
    for (int i = 3; i <= n; i++) {
        ans += dp[i];
    }
    ans %= mod;
    ans *= 2 * n;
    ans %= mod;
    cout << ans << '\n';
    return 0;
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3360kb

input:

1

output:

1

result:

ok single line: '1'

Test #2:

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

input:

2

output:

2

result:

ok single line: '2'

Test #3:

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

input:

3

output:

6

result:

ok single line: '6'

Test #4:

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

input:

4

output:

16

result:

ok single line: '16'

Test #5:

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

input:

5

output:

40

result:

ok single line: '40'

Test #6:

score: 0
Accepted
time: 76ms
memory: 10944kb

input:

1000000

output:

581177467

result:

ok single line: '581177467'

Test #7:

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

input:

6

output:

96

result:

ok single line: '96'

Test #8:

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

input:

7

output:

196

result:

ok single line: '196'

Test #9:

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

input:

8

output:

384

result:

ok single line: '384'

Test #10:

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

input:

9

output:

684

result:

ok single line: '684'

Test #11:

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

input:

10

output:

1200

result:

ok single line: '1200'

Test #12:

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

input:

11

output:

1936

result:

ok single line: '1936'

Test #13:

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

input:

12

output:

3120

result:

ok single line: '3120'

Test #14:

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

input:

13

output:

4732

result:

ok single line: '4732'

Test #15:

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

input:

14

output:

7112

result:

ok single line: '7112'

Test #16:

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

input:

15

output:

10260

result:

ok single line: '10260'

Test #17:

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

input:

16

output:

14784

result:

ok single line: '14784'

Test #18:

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

input:

17

output:

20536

result:

ok single line: '20536'

Test #19:

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

input:

18

output:

28512

result:

ok single line: '28512'

Test #20:

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

input:

19

output:

38380

result:

ok single line: '38380'

Test #21:

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

input:

20

output:

51680

result:

ok single line: '51680'

Test #22:

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

input:

90

output:

775920600

result:

ok single line: '775920600'

Test #23:

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

input:

91

output:

839148492

result:

ok single line: '839148492'

Test #24:

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

input:

92

output:

907941008

result:

ok single line: '907941008'

Test #25:

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

input:

93

output:

980542152

result:

ok single line: '980542152'

Test #26:

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

input:

94

output:

59336753

result:

ok single line: '59336753'

Test #27:

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

input:

95

output:

142357893

result:

ok single line: '142357893'

Test #28:

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

input:

96

output:

232442233

result:

ok single line: '232442233'

Test #29:

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

input:

97

output:

327370109

result:

ok single line: '327370109'

Test #30:

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

input:

98

output:

430140257

result:

ok single line: '430140257'

Test #31:

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

input:

99

output:

538235857

result:

ok single line: '538235857'

Test #32:

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

input:

100

output:

655205993

result:

ok single line: '655205993'

Test #33:

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

input:

9995

output:

97390032

result:

ok single line: '97390032'

Test #34:

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

input:

9996

output:

712595928

result:

ok single line: '712595928'

Test #35:

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

input:

9997

output:

620576335

result:

ok single line: '620576335'

Test #36:

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

input:

9998

output:

988232784

result:

ok single line: '988232784'

Test #37:

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

input:

9999

output:

560204310

result:

ok single line: '560204310'

Test #38:

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

input:

10000

output:

437818049

result:

ok single line: '437818049'

Test #39:

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

input:

99995

output:

458245785

result:

ok single line: '458245785'

Test #40:

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

input:

99996

output:

365965537

result:

ok single line: '365965537'

Test #41:

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

input:

99997

output:

690213069

result:

ok single line: '690213069'

Test #42:

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

input:

99998

output:

366495531

result:

ok single line: '366495531'

Test #43:

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

input:

99999

output:

29029814

result:

ok single line: '29029814'

Test #44:

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

input:

100000

output:

499640718

result:

ok single line: '499640718'

Test #45:

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

input:

199995

output:

608609718

result:

ok single line: '608609718'

Test #46:

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

input:

199996

output:

806298760

result:

ok single line: '806298760'

Test #47:

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

input:

199997

output:

130491354

result:

ok single line: '130491354'

Test #48:

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

input:

199998

output:

677469524

result:

ok single line: '677469524'

Test #49:

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

input:

199999

output:

616525097

result:

ok single line: '616525097'

Test #50:

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

input:

200000

output:

267515275

result:

ok single line: '267515275'

Test #51:

score: 0
Accepted
time: 76ms
memory: 10924kb

input:

999990

output:

34711179

result:

ok single line: '34711179'

Test #52:

score: 0
Accepted
time: 80ms
memory: 10936kb

input:

999991

output:

294717251

result:

ok single line: '294717251'

Test #53:

score: 0
Accepted
time: 82ms
memory: 10932kb

input:

999992

output:

595854721

result:

ok single line: '595854721'

Test #54:

score: 0
Accepted
time: 83ms
memory: 11000kb

input:

999993

output:

702495312

result:

ok single line: '702495312'

Test #55:

score: 0
Accepted
time: 88ms
memory: 10928kb

input:

999994

output:

122168838

result:

ok single line: '122168838'

Test #56:

score: 0
Accepted
time: 83ms
memory: 10956kb

input:

999995

output:

952195638

result:

ok single line: '952195638'

Test #57:

score: 0
Accepted
time: 82ms
memory: 10908kb

input:

999996

output:

960562964

result:

ok single line: '960562964'

Test #58:

score: 0
Accepted
time: 78ms
memory: 10936kb

input:

999997

output:

312380981

result:

ok single line: '312380981'

Test #59:

score: 0
Accepted
time: 82ms
memory: 10936kb

input:

999998

output:

523515513

result:

ok single line: '523515513'

Test #60:

score: 0
Accepted
time: 79ms
memory: 11000kb

input:

999999

output:

163280852

result:

ok single line: '163280852'
English 繁體中文 简体中文

Server Time: 2024-11-29 16:38:34 | OpenSource Project