QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#848295#1651. Modulo PermutationsDriftyAC ✓140ms11752kbC++141.2kb2025-01-08 18:48:482025-01-08 18:48:48

Judging History

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

  • [2025-01-08 18:48:48]
  • 评测
  • 测评结果：AC
  • 用时：140ms
  • 内存：11752kb
查看
  • [2025-01-08 18:48:48]
  • 提交

answer

// Hydro submission #677e580f9649fea3d6ab2d58@1736333327246
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#include <iostream>
#include <string>
#define debug(x) cout << #x << ": " << (x) << "\n";
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
const int maxm = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int p = 1e9 + 7;
ll dp[maxn];
 
int main()
{
    int n;
    scanf("%d", &n);
    if ( n == 1 ) {
        printf("1\n");
        return 0;
    }
    if ( n == 2 ) {
        printf("2\n");
        return 0;
    }
    for ( int i = n;i >= 4;i-- ) {
        dp[i] = 1;
        int temp = 2 * i - 2;
        dp[i] = (dp[i] + dp[i + 1]) % p;
        while ( temp <= n ) {
            dp[i] = (dp[i] + dp[temp]) % p;
            if ( temp + 1 <= n )
                dp[i] = (dp[i] + dp[temp + 1]) % p;
            if ( temp + 2 <= n )
                dp[i] = (dp[i] + dp[temp + 2]) % p;
            temp += i - 1;
        }
    }
    for ( int i = 4;i <= n;i++ ) {
        dp[2] = (dp[2] + dp[i]) % p;
    }
    dp[2] = (2 * dp[2] + 2) % p;
    printf("%lld\n", dp[2] * n % p);
    return 0;
}
 
/*1 1 2 4 8 16 28 48 76 120*/
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1

output:

1

result:

ok single line: '1'

Test #2:

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

input:

2

output:

2

result:

ok single line: '2'

Test #3:

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

input:

3

output:

6

result:

ok single line: '6'

Test #4:

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

input:

4

output:

16

result:

ok single line: '16'

Test #5:

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

input:

5

output:

40

result:

ok single line: '40'

Test #6:

score: 0
Accepted
time: 135ms
memory: 11692kb

input:

1000000

output:

581177467

result:

ok single line: '581177467'

Test #7:

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

input:

6

output:

96

result:

ok single line: '96'

Test #8:

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

input:

7

output:

196

result:

ok single line: '196'

Test #9:

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

input:

8

output:

384

result:

ok single line: '384'

Test #10:

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

input:

9

output:

684

result:

ok single line: '684'

Test #11:

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

input:

10

output:

1200

result:

ok single line: '1200'

Test #12:

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

input:

11

output:

1936

result:

ok single line: '1936'

Test #13:

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

input:

12

output:

3120

result:

ok single line: '3120'

Test #14:

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

input:

13

output:

4732

result:

ok single line: '4732'

Test #15:

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

input:

14

output:

7112

result:

ok single line: '7112'

Test #16:

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

input:

15

output:

10260

result:

ok single line: '10260'

Test #17:

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

input:

16

output:

14784

result:

ok single line: '14784'

Test #18:

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

input:

17

output:

20536

result:

ok single line: '20536'

Test #19:

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

input:

18

output:

28512

result:

ok single line: '28512'

Test #20:

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

input:

19

output:

38380

result:

ok single line: '38380'

Test #21:

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

input:

20

output:

51680

result:

ok single line: '51680'

Test #22:

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

input:

90

output:

775920600

result:

ok single line: '775920600'

Test #23:

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

input:

91

output:

839148492

result:

ok single line: '839148492'

Test #24:

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

input:

92

output:

907941008

result:

ok single line: '907941008'

Test #25:

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

input:

93

output:

980542152

result:

ok single line: '980542152'

Test #26:

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

input:

94

output:

59336753

result:

ok single line: '59336753'

Test #27:

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

input:

95

output:

142357893

result:

ok single line: '142357893'

Test #28:

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

input:

96

output:

232442233

result:

ok single line: '232442233'

Test #29:

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

input:

97

output:

327370109

result:

ok single line: '327370109'

Test #30:

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

input:

98

output:

430140257

result:

ok single line: '430140257'

Test #31:

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

input:

99

output:

538235857

result:

ok single line: '538235857'

Test #32:

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

input:

100

output:

655205993

result:

ok single line: '655205993'

Test #33:

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

input:

9995

output:

97390032

result:

ok single line: '97390032'

Test #34:

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

input:

9996

output:

712595928

result:

ok single line: '712595928'

Test #35:

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

input:

9997

output:

620576335

result:

ok single line: '620576335'

Test #36:

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

input:

9998

output:

988232784

result:

ok single line: '988232784'

Test #37:

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

input:

9999

output:

560204310

result:

ok single line: '560204310'

Test #38:

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

input:

10000

output:

437818049

result:

ok single line: '437818049'

Test #39:

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

input:

99995

output:

458245785

result:

ok single line: '458245785'

Test #40:

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

input:

99996

output:

365965537

result:

ok single line: '365965537'

Test #41:

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

input:

99997

output:

690213069

result:

ok single line: '690213069'

Test #42:

score: 0
Accepted
time: 12ms
memory: 4664kb

input:

99998

output:

366495531

result:

ok single line: '366495531'

Test #43:

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

input:

99999

output:

29029814

result:

ok single line: '29029814'

Test #44:

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

input:

100000

output:

499640718

result:

ok single line: '499640718'

Test #45:

score: 0
Accepted
time: 24ms
memory: 5344kb

input:

199995

output:

608609718

result:

ok single line: '608609718'

Test #46:

score: 0
Accepted
time: 24ms
memory: 5440kb

input:

199996

output:

806298760

result:

ok single line: '806298760'

Test #47:

score: 0
Accepted
time: 24ms
memory: 5444kb

input:

199997

output:

130491354

result:

ok single line: '130491354'

Test #48:

score: 0
Accepted
time: 24ms
memory: 5408kb

input:

199998

output:

677469524

result:

ok single line: '677469524'

Test #49:

score: 0
Accepted
time: 24ms
memory: 5344kb

input:

199999

output:

616525097

result:

ok single line: '616525097'

Test #50:

score: 0
Accepted
time: 25ms
memory: 5436kb

input:

200000

output:

267515275

result:

ok single line: '267515275'

Test #51:

score: 0
Accepted
time: 137ms
memory: 11752kb

input:

999990

output:

34711179

result:

ok single line: '34711179'

Test #52:

score: 0
Accepted
time: 131ms
memory: 11628kb

input:

999991

output:

294717251

result:

ok single line: '294717251'

Test #53:

score: 0
Accepted
time: 138ms
memory: 11752kb

input:

999992

output:

595854721

result:

ok single line: '595854721'

Test #54:

score: 0
Accepted
time: 140ms
memory: 11696kb

input:

999993

output:

702495312

result:

ok single line: '702495312'

Test #55:

score: 0
Accepted
time: 138ms
memory: 11592kb

input:

999994

output:

122168838

result:

ok single line: '122168838'

Test #56:

score: 0
Accepted
time: 133ms
memory: 11596kb

input:

999995

output:

952195638

result:

ok single line: '952195638'

Test #57:

score: 0
Accepted
time: 134ms
memory: 11560kb

input:

999996

output:

960562964

result:

ok single line: '960562964'

Test #58:

score: 0
Accepted
time: 136ms
memory: 11696kb

input:

999997

output:

312380981

result:

ok single line: '312380981'

Test #59:

score: 0
Accepted
time: 132ms
memory: 11556kb

input:

999998

output:

523515513

result:

ok single line: '523515513'

Test #60:

score: 0
Accepted
time: 133ms
memory: 11692kb

input:

999999

output:

163280852

result:

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

Server Time: 2025-01-20 16:58:22 | OpenSource Project