QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#527428#1651. Modulo PermutationsKevin5307#AC ✓934ms129972kbC++231.2kb2024-08-22 15:16:102024-08-22 15:16:11

Judging History

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

  • [2024-08-22 15:16:11]
  • 评测
  • 测评结果:AC
  • 用时:934ms
  • 内存:129972kb
  • [2024-08-22 15:16:10]
  • 提交

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'