QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#373873#5406. 随机游走zhaohaikun100 ✓641ms120880kbC++141.2kb2024-04-02 09:44:352024-04-02 09:44:37

Judging History

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

  • [2024-04-02 09:44:37]
  • 评测
  • 测评结果:100
  • 用时:641ms
  • 内存:120880kb
  • [2024-04-02 09:44:35]
  • 提交

answer

// MagicDark
#include <bits/stdc++.h>
#define debug cerr << "[" << __LINE__ << "] "
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
const int N = 1e7 + 10, MOD = 1e9 + 7;
int n, ans, fac[N], ifac[N], inv[N];
inline void binom(int x) {
	fac[0] = ifac[0] = inv[1] = 1;
	F(i, 2, x) inv[i] = (ll) (MOD - MOD / i) * inv[MOD % i] % MOD;
	F(i, 1, x) fac[i] = (ll) fac[i - 1] * i % MOD, ifac[i] = (ll) ifac[i - 1] * inv[i] % MOD;
}
inline int C(int x, int y) {return x < y || y < 0 ? 0 : (ll) fac[x] * ifac[y] % MOD * ifac[x - y] % MOD;}
inline int power(int x, int y = MOD - 2) {
	int ans = 1;
	for (; y; x = (ll) x * x % MOD, y >>= 1)
		if (y & 1) ans = (ll) ans * x % MOD;
	return ans;
}
inline void add(int &x, ll y) {x = (x + y) % MOD;}
signed main() {
	binom(N - 1);
	cin >> n;
	F(i, 0, n) {
		int w = 2ll * ifac[2 * n + 1] % MOD * power(n - i, 2 * n + 1) % MOD * C(2 * n, i) % MOD;
		if (i & 1) add(ans, MOD - w);
		else add(ans, w);
	}
	cout << ans;
	return 0;
}
/* why?
*/

詳細信息

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 98ms
memory: 120672kb

input:

1

output:

333333336

result:

ok 1 number(s): "333333336"

Test #2:

score: 0
Accepted
time: 99ms
memory: 120844kb

input:

2

output:

266666669

result:

ok 1 number(s): "266666669"

Test #3:

score: 0
Accepted
time: 89ms
memory: 120776kb

input:

3

output:

769047625

result:

ok 1 number(s): "769047625"

Subtask #2:

score: 10
Accepted

Test #4:

score: 10
Accepted
time: 91ms
memory: 120844kb

input:

4

output:

877865968

result:

ok 1 number(s): "877865968"

Test #5:

score: 0
Accepted
time: 93ms
memory: 120672kb

input:

5

output:

733342859

result:

ok 1 number(s): "733342859"

Test #6:

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

input:

6

output:

655899114

result:

ok 1 number(s): "655899114"

Test #7:

score: 0
Accepted
time: 104ms
memory: 120780kb

input:

7

output:

946326757

result:

ok 1 number(s): "946326757"

Test #8:

score: 0
Accepted
time: 102ms
memory: 120840kb

input:

8

output:

230714822

result:

ok 1 number(s): "230714822"

Test #9:

score: 0
Accepted
time: 96ms
memory: 120820kb

input:

9

output:

782967541

result:

ok 1 number(s): "782967541"

Test #10:

score: 0
Accepted
time: 91ms
memory: 120784kb

input:

10

output:

732371611

result:

ok 1 number(s): "732371611"

Subtask #3:

score: 10
Accepted

Test #11:

score: 10
Accepted
time: 91ms
memory: 120716kb

input:

15

output:

677123472

result:

ok 1 number(s): "677123472"

Test #12:

score: 0
Accepted
time: 101ms
memory: 120784kb

input:

13

output:

168974634

result:

ok 1 number(s): "168974634"

Test #13:

score: 0
Accepted
time: 89ms
memory: 120788kb

input:

26

output:

213343876

result:

ok 1 number(s): "213343876"

Test #14:

score: 0
Accepted
time: 101ms
memory: 120840kb

input:

29

output:

631124616

result:

ok 1 number(s): "631124616"

Subtask #4:

score: 15
Accepted

Test #15:

score: 15
Accepted
time: 93ms
memory: 120668kb

input:

37

output:

349256161

result:

ok 1 number(s): "349256161"

Test #16:

score: 0
Accepted
time: 104ms
memory: 120668kb

input:

104

output:

351095881

result:

ok 1 number(s): "351095881"

Test #17:

score: 0
Accepted
time: 88ms
memory: 120848kb

input:

194

output:

895504391

result:

ok 1 number(s): "895504391"

Test #18:

score: 0
Accepted
time: 91ms
memory: 120776kb

input:

197

output:

923555376

result:

ok 1 number(s): "923555376"

Test #19:

score: 0
Accepted
time: 88ms
memory: 120776kb

input:

198

output:

512220517

result:

ok 1 number(s): "512220517"

Subtask #5:

score: 15
Accepted

Test #20:

score: 15
Accepted
time: 101ms
memory: 120792kb

input:

562

output:

255062346

result:

ok 1 number(s): "255062346"

Test #21:

score: 0
Accepted
time: 102ms
memory: 120788kb

input:

1007

output:

735041605

result:

ok 1 number(s): "735041605"

Test #22:

score: 0
Accepted
time: 99ms
memory: 120780kb

input:

1788

output:

208261384

result:

ok 1 number(s): "208261384"

Test #23:

score: 0
Accepted
time: 83ms
memory: 120824kb

input:

1980

output:

875427987

result:

ok 1 number(s): "875427987"

Test #24:

score: 0
Accepted
time: 99ms
memory: 120788kb

input:

1983

output:

571776252

result:

ok 1 number(s): "571776252"

Test #25:

score: 0
Accepted
time: 84ms
memory: 120848kb

input:

1992

output:

12983695

result:

ok 1 number(s): "12983695"

Subtask #6:

score: 15
Accepted

Test #26:

score: 15
Accepted
time: 103ms
memory: 120792kb

input:

3946

output:

977435333

result:

ok 1 number(s): "977435333"

Test #27:

score: 0
Accepted
time: 98ms
memory: 120788kb

input:

65944

output:

312666196

result:

ok 1 number(s): "312666196"

Test #28:

score: 0
Accepted
time: 116ms
memory: 120788kb

input:

163815

output:

163767254

result:

ok 1 number(s): "163767254"

Test #29:

score: 0
Accepted
time: 115ms
memory: 120732kb

input:

198732

output:

911833524

result:

ok 1 number(s): "911833524"

Test #30:

score: 0
Accepted
time: 109ms
memory: 120780kb

input:

199287

output:

910277128

result:

ok 1 number(s): "910277128"

Test #31:

score: 0
Accepted
time: 121ms
memory: 120764kb

input:

199819

output:

561747634

result:

ok 1 number(s): "561747634"

Subtask #7:

score: 30
Accepted

Test #32:

score: 30
Accepted
time: 118ms
memory: 120668kb

input:

315618

output:

602805814

result:

ok 1 number(s): "602805814"

Test #33:

score: 0
Accepted
time: 212ms
memory: 120880kb

input:

1130465

output:

898203793

result:

ok 1 number(s): "898203793"

Test #34:

score: 0
Accepted
time: 552ms
memory: 120792kb

input:

4399723

output:

101317224

result:

ok 1 number(s): "101317224"

Test #35:

score: 0
Accepted
time: 603ms
memory: 120820kb

input:

4804460

output:

114947085

result:

ok 1 number(s): "114947085"

Test #36:

score: 0
Accepted
time: 623ms
memory: 120788kb

input:

4995726

output:

460040939

result:

ok 1 number(s): "460040939"

Test #37:

score: 0
Accepted
time: 641ms
memory: 120672kb

input:

4999919

output:

780785591

result:

ok 1 number(s): "780785591"

Test #38:

score: 0
Accepted
time: 626ms
memory: 120792kb

input:

4999999

output:

742624725

result:

ok 1 number(s): "742624725"