QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#363861 | #1651. Modulo Permutations | kevinyang# | AC ✓ | 65ms | 7604kb | C++17 | 1.4kb | 2024-03-24 04:25:41 | 2024-03-24 04:25:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int mod = (int)1e9+7;
int dp[1000005];
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
int n;
cin >> n;
if(n==1){
cout << "1\n";
return 0;
}
dp[2] = 1;
//dp[i] represents number of solutions where you start building from (i-1,i)
//starting from (1,2)
//answer for n is the sum of number of ways to build from (i-1,i)
//how to build from i-1, i
//you can go from i-1,i to j-1,j if
//j-1,i-1 is good, j,i, is good, j,j-1 is good, or j-1,i is good
//each of those options, add to answer
// j-1, j -> i-1, i
dp[3] = 1;
dp[4] = 2;
/*
(2,3) -> 1
(1,2) -> 1
(3,4) -> 2
4 1 3 2
4 2 3 1
3 2 1
5 4
(3,4) -> (3,5) -> (6,5)
(2,3) -> (3,4) -> (3,5) -> (6,5)
(4,5) -> (6,5)
*/
// dp[5] = 4;
for(int i = 5; i<=n; i++){
dp[i] = 2;
}
for(int i = 4; i<=n; i++){
for(int j = (i-1)*2; j<=n; j+=i-1){
dp[j+1]+=dp[i];
dp[j+2]+=dp[i];
dp[j]+=dp[i];
dp[j+1]%=mod;
dp[j+2]%=mod;
dp[j]%=mod;
}
dp[i+1]+=dp[i];
dp[i+1]%=mod;
}
long long ans = 0;
for(int i = 2; i<=n; i++){
ans+=dp[i];
ans%=mod;
}
cout << ans*n%mod << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3640kb
input:
1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
2
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
3
output:
6
result:
ok single line: '6'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
4
output:
16
result:
ok single line: '16'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
5
output:
40
result:
ok single line: '40'
Test #6:
score: 0
Accepted
time: 61ms
memory: 7544kb
input:
1000000
output:
581177467
result:
ok single line: '581177467'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
6
output:
96
result:
ok single line: '96'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
7
output:
196
result:
ok single line: '196'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
8
output:
384
result:
ok single line: '384'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
9
output:
684
result:
ok single line: '684'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
10
output:
1200
result:
ok single line: '1200'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
11
output:
1936
result:
ok single line: '1936'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
12
output:
3120
result:
ok single line: '3120'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
13
output:
4732
result:
ok single line: '4732'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
14
output:
7112
result:
ok single line: '7112'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
15
output:
10260
result:
ok single line: '10260'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
16
output:
14784
result:
ok single line: '14784'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
17
output:
20536
result:
ok single line: '20536'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
18
output:
28512
result:
ok single line: '28512'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
19
output:
38380
result:
ok single line: '38380'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
20
output:
51680
result:
ok single line: '51680'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
90
output:
775920600
result:
ok single line: '775920600'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
91
output:
839148492
result:
ok single line: '839148492'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
92
output:
907941008
result:
ok single line: '907941008'
Test #25:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
93
output:
980542152
result:
ok single line: '980542152'
Test #26:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
94
output:
59336753
result:
ok single line: '59336753'
Test #27:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
95
output:
142357893
result:
ok single line: '142357893'
Test #28:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
96
output:
232442233
result:
ok single line: '232442233'
Test #29:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
97
output:
327370109
result:
ok single line: '327370109'
Test #30:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
98
output:
430140257
result:
ok single line: '430140257'
Test #31:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
99
output:
538235857
result:
ok single line: '538235857'
Test #32:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
100
output:
655205993
result:
ok single line: '655205993'
Test #33:
score: 0
Accepted
time: 1ms
memory: 3616kb
input:
9995
output:
97390032
result:
ok single line: '97390032'
Test #34:
score: 0
Accepted
time: 1ms
memory: 3676kb
input:
9996
output:
712595928
result:
ok single line: '712595928'
Test #35:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
9997
output:
620576335
result:
ok single line: '620576335'
Test #36:
score: 0
Accepted
time: 1ms
memory: 3596kb
input:
9998
output:
988232784
result:
ok single line: '988232784'
Test #37:
score: 0
Accepted
time: 1ms
memory: 3676kb
input:
9999
output:
560204310
result:
ok single line: '560204310'
Test #38:
score: 0
Accepted
time: 1ms
memory: 3736kb
input:
10000
output:
437818049
result:
ok single line: '437818049'
Test #39:
score: 0
Accepted
time: 4ms
memory: 4028kb
input:
99995
output:
458245785
result:
ok single line: '458245785'
Test #40:
score: 0
Accepted
time: 2ms
memory: 5644kb
input:
99996
output:
365965537
result:
ok single line: '365965537'
Test #41:
score: 0
Accepted
time: 4ms
memory: 5872kb
input:
99997
output:
690213069
result:
ok single line: '690213069'
Test #42:
score: 0
Accepted
time: 4ms
memory: 4008kb
input:
99998
output:
366495531
result:
ok single line: '366495531'
Test #43:
score: 0
Accepted
time: 4ms
memory: 4108kb
input:
99999
output:
29029814
result:
ok single line: '29029814'
Test #44:
score: 0
Accepted
time: 4ms
memory: 4016kb
input:
100000
output:
499640718
result:
ok single line: '499640718'
Test #45:
score: 0
Accepted
time: 7ms
memory: 5788kb
input:
199995
output:
608609718
result:
ok single line: '608609718'
Test #46:
score: 0
Accepted
time: 7ms
memory: 5764kb
input:
199996
output:
806298760
result:
ok single line: '806298760'
Test #47:
score: 0
Accepted
time: 7ms
memory: 5856kb
input:
199997
output:
130491354
result:
ok single line: '130491354'
Test #48:
score: 0
Accepted
time: 8ms
memory: 4468kb
input:
199998
output:
677469524
result:
ok single line: '677469524'
Test #49:
score: 0
Accepted
time: 8ms
memory: 5672kb
input:
199999
output:
616525097
result:
ok single line: '616525097'
Test #50:
score: 0
Accepted
time: 8ms
memory: 6268kb
input:
200000
output:
267515275
result:
ok single line: '267515275'
Test #51:
score: 0
Accepted
time: 61ms
memory: 7528kb
input:
999990
output:
34711179
result:
ok single line: '34711179'
Test #52:
score: 0
Accepted
time: 61ms
memory: 7472kb
input:
999991
output:
294717251
result:
ok single line: '294717251'
Test #53:
score: 0
Accepted
time: 64ms
memory: 7528kb
input:
999992
output:
595854721
result:
ok single line: '595854721'
Test #54:
score: 0
Accepted
time: 65ms
memory: 7468kb
input:
999993
output:
702495312
result:
ok single line: '702495312'
Test #55:
score: 0
Accepted
time: 60ms
memory: 7540kb
input:
999994
output:
122168838
result:
ok single line: '122168838'
Test #56:
score: 0
Accepted
time: 64ms
memory: 7452kb
input:
999995
output:
952195638
result:
ok single line: '952195638'
Test #57:
score: 0
Accepted
time: 65ms
memory: 7480kb
input:
999996
output:
960562964
result:
ok single line: '960562964'
Test #58:
score: 0
Accepted
time: 64ms
memory: 7544kb
input:
999997
output:
312380981
result:
ok single line: '312380981'
Test #59:
score: 0
Accepted
time: 64ms
memory: 7532kb
input:
999998
output:
523515513
result:
ok single line: '523515513'
Test #60:
score: 0
Accepted
time: 64ms
memory: 7604kb
input:
999999
output:
163280852
result:
ok single line: '163280852'