QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#687701#1651. Modulo PermutationsRepeaterAC ✓69ms11112kbC++20688b2024-10-29 20:35:482024-10-29 20:35:48

Judging History

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

  • [2024-10-29 20:35:48]
  • 评测
  • 测评结果：AC
  • 用时：69ms
  • 内存：11112kb
查看
  • [2024-10-29 20:35:48]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;

constexpr int P = 1e9 + 7;

void add(i64 &a, i64 b)
{
	a += b;
	if(a >= P) a -= P;
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int n; std::cin >> n;
	if(n == 1)
	{
		std::cout << 1 << "\n";
		return 0;
	}

	std::vector<i64> f(n + 1);
	f[1] = 1;

	for(int j = 1; j <= n - 1; j++)
	{
		if(j <= 3) for(int i = j + 1; i <= n; i++) 
			add(f[i], f[j]);
		else for(int k = -1; k <= 1; k++)
			for(int i = j + k; i < n; i += j) if(i > j)
				add(f[i], f[j]);
	}

	i64 ans = 0;
	for(int i = 0; i < n; i++) add(ans, f[i]);

	std::cout << n * ans % P << "\n";

	return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3772kb

input:

1

output:

1

result:

ok single line: '1'

Test #2:

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

input:

2

output:

2

result:

ok single line: '2'

Test #3:

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

input:

3

output:

6

result:

ok single line: '6'

Test #4:

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

input:

4

output:

16

result:

ok single line: '16'

Test #5:

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

input:

5

output:

40

result:

ok single line: '40'

Test #6:

score: 0
Accepted
time: 64ms
memory: 11000kb

input:

1000000

output:

581177467

result:

ok single line: '581177467'

Test #7:

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

input:

6

output:

96

result:

ok single line: '96'

Test #8:

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

input:

7

output:

196

result:

ok single line: '196'

Test #9:

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

input:

8

output:

384

result:

ok single line: '384'

Test #10:

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

input:

9

output:

684

result:

ok single line: '684'

Test #11:

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

input:

10

output:

1200

result:

ok single line: '1200'

Test #12:

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

input:

11

output:

1936

result:

ok single line: '1936'

Test #13:

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

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: 3620kb

input:

14

output:

7112

result:

ok single line: '7112'

Test #16:

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

input:

15

output:

10260

result:

ok single line: '10260'

Test #17:

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

input:

16

output:

14784

result:

ok single line: '14784'

Test #18:

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

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: 3592kb

input:

19

output:

38380

result:

ok single line: '38380'

Test #21:

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

input:

20

output:

51680

result:

ok single line: '51680'

Test #22:

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

input:

90

output:

775920600

result:

ok single line: '775920600'

Test #23:

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

input:

91

output:

839148492

result:

ok single line: '839148492'

Test #24:

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

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: 3620kb

input:

94

output:

59336753

result:

ok single line: '59336753'

Test #27:

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

input:

95

output:

142357893

result:

ok single line: '142357893'

Test #28:

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

input:

96

output:

232442233

result:

ok single line: '232442233'

Test #29:

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

input:

97

output:

327370109

result:

ok single line: '327370109'

Test #30:

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

input:

98

output:

430140257

result:

ok single line: '430140257'

Test #31:

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

input:

99

output:

538235857

result:

ok single line: '538235857'

Test #32:

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

input:

100

output:

655205993

result:

ok single line: '655205993'

Test #33:

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

input:

9995

output:

97390032

result:

ok single line: '97390032'

Test #34:

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

input:

9996

output:

712595928

result:

ok single line: '712595928'

Test #35:

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

input:

9997

output:

620576335

result:

ok single line: '620576335'

Test #36:

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

input:

9998

output:

988232784

result:

ok single line: '988232784'

Test #37:

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

input:

9999

output:

560204310

result:

ok single line: '560204310'

Test #38:

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

input:

10000

output:

437818049

result:

ok single line: '437818049'

Test #39:

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

input:

99995

output:

458245785

result:

ok single line: '458245785'

Test #40:

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

input:

99996

output:

365965537

result:

ok single line: '365965537'

Test #41:

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

input:

99997

output:

690213069

result:

ok single line: '690213069'

Test #42:

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

input:

99998

output:

366495531

result:

ok single line: '366495531'

Test #43:

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

input:

99999

output:

29029814

result:

ok single line: '29029814'

Test #44:

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

input:

100000

output:

499640718

result:

ok single line: '499640718'

Test #45:

score: 0
Accepted
time: 6ms
memory: 4620kb

input:

199995

output:

608609718

result:

ok single line: '608609718'

Test #46:

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

input:

199996

output:

806298760

result:

ok single line: '806298760'

Test #47:

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

input:

199997

output:

130491354

result:

ok single line: '130491354'

Test #48:

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

input:

199998

output:

677469524

result:

ok single line: '677469524'

Test #49:

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

input:

199999

output:

616525097

result:

ok single line: '616525097'

Test #50:

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

input:

200000

output:

267515275

result:

ok single line: '267515275'

Test #51:

score: 0
Accepted
time: 69ms
memory: 11024kb

input:

999990

output:

34711179

result:

ok single line: '34711179'

Test #52:

score: 0
Accepted
time: 64ms
memory: 11032kb

input:

999991

output:

294717251

result:

ok single line: '294717251'

Test #53:

score: 0
Accepted
time: 63ms
memory: 11072kb

input:

999992

output:

595854721

result:

ok single line: '595854721'

Test #54:

score: 0
Accepted
time: 62ms
memory: 11088kb

input:

999993

output:

702495312

result:

ok single line: '702495312'

Test #55:

score: 0
Accepted
time: 64ms
memory: 11104kb

input:

999994

output:

122168838

result:

ok single line: '122168838'

Test #56:

score: 0
Accepted
time: 61ms
memory: 10968kb

input:

999995

output:

952195638

result:

ok single line: '952195638'

Test #57:

score: 0
Accepted
time: 63ms
memory: 11104kb

input:

999996

output:

960562964

result:

ok single line: '960562964'

Test #58:

score: 0
Accepted
time: 63ms
memory: 11108kb

input:

999997

output:

312380981

result:

ok single line: '312380981'

Test #59:

score: 0
Accepted
time: 64ms
memory: 11112kb

input:

999998

output:

523515513

result:

ok single line: '523515513'

Test #60:

score: 0
Accepted
time: 60ms
memory: 11044kb

input:

999999

output:

163280852

result:

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

Server Time: 2024-11-29 16:35:50 | OpenSource Project