QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#590354#1651. Modulo Permutationsucup-team3474#AC ✓144ms20744kbC++20873b2024-09-25 23:31:272024-09-25 23:31:27

Judging History

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

  • [2024-09-25 23:31:27]
  • 评测
  • 测评结果：AC
  • 用时：144ms
  • 内存：20744kb
查看
  • [2024-09-25 23:31:27]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1919810,mod=1e9+7;
typedef long long ll;
typedef pair<ll,ll> PII;
ll n,m,k;
ll a[N],b[N];
char s[N];

ll dp[N];

void __(){
    scanf("%d",&n);
    memset(dp,0,sizeof dp);
    if(n==1) puts("1");
    else if(n==2) puts("2");
    else{
        dp[n+1]=1;
        for(int i=n;i>=3;i--){
            for(int j=i;j<=n;j+=i){
                for(int k=j;k<=j+2;k++){
                    if(k<=n&&k!=i&&k!=i+1){
                        dp[i+1]=(dp[i+1]+dp[k])%mod;
                    }
                }
            }
            dp[i+1]++;
            dp[i+1]%=mod;
        }
        ll sum=0;
        for(int i=3;i<=n;i++) sum=(sum+dp[i])%mod;
        printf("%lld\n",(sum*2*n+2*n)%mod);
    }
}


int main(){
    int _=1;
    // cin>>_;
    while(_--){
        __();
    }
}
源文件, 语言: C++20

詳細信息

Test #1:

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

input:

1

output:

1

result:

ok single line: '1'

Test #2:

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

input:

2

output:

2

result:

ok single line: '2'

Test #3:

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

input:

3

output:

6

result:

ok single line: '6'

Test #4:

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

input:

4

output:

16

result:

ok single line: '16'

Test #5:

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

input:

5

output:

40

result:

ok single line: '40'

Test #6:

score: 0
Accepted
time: 142ms
memory: 19444kb

input:

1000000

output:

581177467

result:

ok single line: '581177467'

Test #7:

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

input:

6

output:

96

result:

ok single line: '96'

Test #8:

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

input:

7

output:

196

result:

ok single line: '196'

Test #9:

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

input:

8

output:

384

result:

ok single line: '384'

Test #10:

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

input:

9

output:

684

result:

ok single line: '684'

Test #11:

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

input:

10

output:

1200

result:

ok single line: '1200'

Test #12:

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

input:

11

output:

1936

result:

ok single line: '1936'

Test #13:

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

input:

12

output:

3120

result:

ok single line: '3120'

Test #14:

score: 0
Accepted
time: 4ms
memory: 19316kb

input:

13

output:

4732

result:

ok single line: '4732'

Test #15:

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

input:

14

output:

7112

result:

ok single line: '7112'

Test #16:

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

input:

15

output:

10260

result:

ok single line: '10260'

Test #17:

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

input:

16

output:

14784

result:

ok single line: '14784'

Test #18:

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

input:

17

output:

20536

result:

ok single line: '20536'

Test #19:

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

input:

18

output:

28512

result:

ok single line: '28512'

Test #20:

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

input:

19

output:

38380

result:

ok single line: '38380'

Test #21:

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

input:

20

output:

51680

result:

ok single line: '51680'

Test #22:

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

input:

90

output:

775920600

result:

ok single line: '775920600'

Test #23:

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

input:

91

output:

839148492

result:

ok single line: '839148492'

Test #24:

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

input:

92

output:

907941008

result:

ok single line: '907941008'

Test #25:

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

input:

93

output:

980542152

result:

ok single line: '980542152'

Test #26:

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

input:

94

output:

59336753

result:

ok single line: '59336753'

Test #27:

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

input:

95

output:

142357893

result:

ok single line: '142357893'

Test #28:

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

input:

96

output:

232442233

result:

ok single line: '232442233'

Test #29:

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

input:

97

output:

327370109

result:

ok single line: '327370109'

Test #30:

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

input:

98

output:

430140257

result:

ok single line: '430140257'

Test #31:

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

input:

99

output:

538235857

result:

ok single line: '538235857'

Test #32:

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

input:

100

output:

655205993

result:

ok single line: '655205993'

Test #33:

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

input:

9995

output:

97390032

result:

ok single line: '97390032'

Test #34:

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

input:

9996

output:

712595928

result:

ok single line: '712595928'

Test #35:

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

input:

9997

output:

620576335

result:

ok single line: '620576335'

Test #36:

score: 0
Accepted
time: 4ms
memory: 20184kb

input:

9998

output:

988232784

result:

ok single line: '988232784'

Test #37:

score: 0
Accepted
time: 4ms
memory: 20608kb

input:

9999

output:

560204310

result:

ok single line: '560204310'

Test #38:

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

input:

10000

output:

437818049

result:

ok single line: '437818049'

Test #39:

score: 0
Accepted
time: 13ms
memory: 18908kb

input:

99995

output:

458245785

result:

ok single line: '458245785'

Test #40:

score: 0
Accepted
time: 14ms
memory: 19816kb

input:

99996

output:

365965537

result:

ok single line: '365965537'

Test #41:

score: 0
Accepted
time: 9ms
memory: 20508kb

input:

99997

output:

690213069

result:

ok single line: '690213069'

Test #42:

score: 0
Accepted
time: 10ms
memory: 19100kb

input:

99998

output:

366495531

result:

ok single line: '366495531'

Test #43:

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

input:

99999

output:

29029814

result:

ok single line: '29029814'

Test #44:

score: 0
Accepted
time: 14ms
memory: 19336kb

input:

100000

output:

499640718

result:

ok single line: '499640718'

Test #45:

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

input:

199995

output:

608609718

result:

ok single line: '608609718'

Test #46:

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

input:

199996

output:

806298760

result:

ok single line: '806298760'

Test #47:

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

input:

199997

output:

130491354

result:

ok single line: '130491354'

Test #48:

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

input:

199998

output:

677469524

result:

ok single line: '677469524'

Test #49:

score: 0
Accepted
time: 26ms
memory: 19088kb

input:

199999

output:

616525097

result:

ok single line: '616525097'

Test #50:

score: 0
Accepted
time: 26ms
memory: 19036kb

input:

200000

output:

267515275

result:

ok single line: '267515275'

Test #51:

score: 0
Accepted
time: 144ms
memory: 20672kb

input:

999990

output:

34711179

result:

ok single line: '34711179'

Test #52:

score: 0
Accepted
time: 139ms
memory: 19872kb

input:

999991

output:

294717251

result:

ok single line: '294717251'

Test #53:

score: 0
Accepted
time: 142ms
memory: 19716kb

input:

999992

output:

595854721

result:

ok single line: '595854721'

Test #54:

score: 0
Accepted
time: 141ms
memory: 20364kb

input:

999993

output:

702495312

result:

ok single line: '702495312'

Test #55:

score: 0
Accepted
time: 139ms
memory: 20728kb

input:

999994

output:

122168838

result:

ok single line: '122168838'

Test #56:

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

input:

999995

output:

952195638

result:

ok single line: '952195638'

Test #57:

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

input:

999996

output:

960562964

result:

ok single line: '960562964'

Test #58:

score: 0
Accepted
time: 142ms
memory: 20744kb

input:

999997

output:

312380981

result:

ok single line: '312380981'

Test #59:

score: 0
Accepted
time: 139ms
memory: 20496kb

input:

999998

output:

523515513

result:

ok single line: '523515513'

Test #60:

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

input:

999999

output:

163280852

result:

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

伺服器時間: 2024-11-29 16:27:46 | 開源專案