QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#527428 | #1651. Modulo Permutations | Kevin5307# | AC ✓ | 934ms | 129972kb | C++23 | 1.2kb | 2024-08-22 15:16:10 | 2024-08-22 15:16:11 |
Judging History
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
const ll mod=1e9+7;
ll dp[1001000];
vector<int> vd[1001000];
int vis[1001000];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
dp[1]=1;
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j+=i)
vd[j].pb(i);
for(int i=3;i<=n;i++)
{
vector<int> vv;
for(int j=i-2;j<=i;j++)
for(auto x:vd[j])
vv.pb(x);
for(auto x:vv) if(x<i-1)
{
if(!vis[x]) vis[x]=1;
else continue;
dp[i-1]=(dp[i-1]+dp[x])%mod;
}
for(auto x:vv) vis[x]=0;
}
ll ans=accumulate(dp+1,dp+n+1,0ll)%mod;
cout<<ans*n%mod<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5924kb
input:
1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 1ms
memory: 5584kb
input:
2
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 1ms
memory: 5624kb
input:
3
output:
6
result:
ok single line: '6'
Test #4:
score: 0
Accepted
time: 0ms
memory: 5620kb
input:
4
output:
16
result:
ok single line: '16'
Test #5:
score: 0
Accepted
time: 1ms
memory: 5688kb
input:
5
output:
40
result:
ok single line: '40'
Test #6:
score: 0
Accepted
time: 896ms
memory: 129672kb
input:
1000000
output:
581177467
result:
ok single line: '581177467'
Test #7:
score: 0
Accepted
time: 2ms
memory: 5724kb
input:
6
output:
96
result:
ok single line: '96'
Test #8:
score: 0
Accepted
time: 2ms
memory: 5636kb
input:
7
output:
196
result:
ok single line: '196'
Test #9:
score: 0
Accepted
time: 1ms
memory: 5688kb
input:
8
output:
384
result:
ok single line: '384'
Test #10:
score: 0
Accepted
time: 0ms
memory: 5628kb
input:
9
output:
684
result:
ok single line: '684'
Test #11:
score: 0
Accepted
time: 1ms
memory: 5628kb
input:
10
output:
1200
result:
ok single line: '1200'
Test #12:
score: 0
Accepted
time: 1ms
memory: 5624kb
input:
11
output:
1936
result:
ok single line: '1936'
Test #13:
score: 0
Accepted
time: 1ms
memory: 5580kb
input:
12
output:
3120
result:
ok single line: '3120'
Test #14:
score: 0
Accepted
time: 1ms
memory: 5624kb
input:
13
output:
4732
result:
ok single line: '4732'
Test #15:
score: 0
Accepted
time: 1ms
memory: 5580kb
input:
14
output:
7112
result:
ok single line: '7112'
Test #16:
score: 0
Accepted
time: 1ms
memory: 5624kb
input:
15
output:
10260
result:
ok single line: '10260'
Test #17:
score: 0
Accepted
time: 1ms
memory: 5636kb
input:
16
output:
14784
result:
ok single line: '14784'
Test #18:
score: 0
Accepted
time: 0ms
memory: 5684kb
input:
17
output:
20536
result:
ok single line: '20536'
Test #19:
score: 0
Accepted
time: 0ms
memory: 5688kb
input:
18
output:
28512
result:
ok single line: '28512'
Test #20:
score: 0
Accepted
time: 1ms
memory: 5852kb
input:
19
output:
38380
result:
ok single line: '38380'
Test #21:
score: 0
Accepted
time: 1ms
memory: 5684kb
input:
20
output:
51680
result:
ok single line: '51680'
Test #22:
score: 0
Accepted
time: 1ms
memory: 5692kb
input:
90
output:
775920600
result:
ok single line: '775920600'
Test #23:
score: 0
Accepted
time: 1ms
memory: 5704kb
input:
91
output:
839148492
result:
ok single line: '839148492'
Test #24:
score: 0
Accepted
time: 0ms
memory: 5692kb
input:
92
output:
907941008
result:
ok single line: '907941008'
Test #25:
score: 0
Accepted
time: 0ms
memory: 5856kb
input:
93
output:
980542152
result:
ok single line: '980542152'
Test #26:
score: 0
Accepted
time: 1ms
memory: 5632kb
input:
94
output:
59336753
result:
ok single line: '59336753'
Test #27:
score: 0
Accepted
time: 1ms
memory: 5900kb
input:
95
output:
142357893
result:
ok single line: '142357893'
Test #28:
score: 0
Accepted
time: 1ms
memory: 5936kb
input:
96
output:
232442233
result:
ok single line: '232442233'
Test #29:
score: 0
Accepted
time: 0ms
memory: 5924kb
input:
97
output:
327370109
result:
ok single line: '327370109'
Test #30:
score: 0
Accepted
time: 1ms
memory: 5856kb
input:
98
output:
430140257
result:
ok single line: '430140257'
Test #31:
score: 0
Accepted
time: 1ms
memory: 5860kb
input:
99
output:
538235857
result:
ok single line: '538235857'
Test #32:
score: 0
Accepted
time: 0ms
memory: 5692kb
input:
100
output:
655205993
result:
ok single line: '655205993'
Test #33:
score: 0
Accepted
time: 5ms
memory: 6632kb
input:
9995
output:
97390032
result:
ok single line: '97390032'
Test #34:
score: 0
Accepted
time: 3ms
memory: 6928kb
input:
9996
output:
712595928
result:
ok single line: '712595928'
Test #35:
score: 0
Accepted
time: 6ms
memory: 6904kb
input:
9997
output:
620576335
result:
ok single line: '620576335'
Test #36:
score: 0
Accepted
time: 6ms
memory: 6856kb
input:
9998
output:
988232784
result:
ok single line: '988232784'
Test #37:
score: 0
Accepted
time: 5ms
memory: 6632kb
input:
9999
output:
560204310
result:
ok single line: '560204310'
Test #38:
score: 0
Accepted
time: 5ms
memory: 6628kb
input:
10000
output:
437818049
result:
ok single line: '437818049'
Test #39:
score: 0
Accepted
time: 56ms
memory: 17020kb
input:
99995
output:
458245785
result:
ok single line: '458245785'
Test #40:
score: 0
Accepted
time: 59ms
memory: 17228kb
input:
99996
output:
365965537
result:
ok single line: '365965537'
Test #41:
score: 0
Accepted
time: 53ms
memory: 16456kb
input:
99997
output:
690213069
result:
ok single line: '690213069'
Test #42:
score: 0
Accepted
time: 57ms
memory: 16744kb
input:
99998
output:
366495531
result:
ok single line: '366495531'
Test #43:
score: 0
Accepted
time: 60ms
memory: 16292kb
input:
99999
output:
29029814
result:
ok single line: '29029814'
Test #44:
score: 0
Accepted
time: 59ms
memory: 16392kb
input:
100000
output:
499640718
result:
ok single line: '499640718'
Test #45:
score: 0
Accepted
time: 115ms
memory: 29300kb
input:
199995
output:
608609718
result:
ok single line: '608609718'
Test #46:
score: 0
Accepted
time: 121ms
memory: 29300kb
input:
199996
output:
806298760
result:
ok single line: '806298760'
Test #47:
score: 0
Accepted
time: 120ms
memory: 29612kb
input:
199997
output:
130491354
result:
ok single line: '130491354'
Test #48:
score: 0
Accepted
time: 118ms
memory: 28920kb
input:
199998
output:
677469524
result:
ok single line: '677469524'
Test #49:
score: 0
Accepted
time: 118ms
memory: 28376kb
input:
199999
output:
616525097
result:
ok single line: '616525097'
Test #50:
score: 0
Accepted
time: 111ms
memory: 31448kb
input:
200000
output:
267515275
result:
ok single line: '267515275'
Test #51:
score: 0
Accepted
time: 933ms
memory: 129732kb
input:
999990
output:
34711179
result:
ok single line: '34711179'
Test #52:
score: 0
Accepted
time: 905ms
memory: 129972kb
input:
999991
output:
294717251
result:
ok single line: '294717251'
Test #53:
score: 0
Accepted
time: 905ms
memory: 129888kb
input:
999992
output:
595854721
result:
ok single line: '595854721'
Test #54:
score: 0
Accepted
time: 892ms
memory: 129972kb
input:
999993
output:
702495312
result:
ok single line: '702495312'
Test #55:
score: 0
Accepted
time: 899ms
memory: 129936kb
input:
999994
output:
122168838
result:
ok single line: '122168838'
Test #56:
score: 0
Accepted
time: 934ms
memory: 129672kb
input:
999995
output:
952195638
result:
ok single line: '952195638'
Test #57:
score: 0
Accepted
time: 926ms
memory: 129708kb
input:
999996
output:
960562964
result:
ok single line: '960562964'
Test #58:
score: 0
Accepted
time: 901ms
memory: 129660kb
input:
999997
output:
312380981
result:
ok single line: '312380981'
Test #59:
score: 0
Accepted
time: 891ms
memory: 129776kb
input:
999998
output:
523515513
result:
ok single line: '523515513'
Test #60:
score: 0
Accepted
time: 929ms
memory: 129736kb
input:
999999
output:
163280852
result:
ok single line: '163280852'