QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#262601#5406. 随机游走EverlastingEternity100 ✓168ms213856kbC++142.6kb2023-11-23 20:45:262023-11-23 20:45:27

Judging History

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

  • [2023-11-23 20:45:27]
  • 评测
  • 测评结果:100
  • 用时:168ms
  • 内存:213856kb
  • [2023-11-23 20:45:26]
  • 提交

answer

#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;

bool _u;

using ll = long long;
using db = double;
using pii = pair <int, int> ;
using vi = vector <int> ;
#define ci const int
template <class T>
inline void chmax(T &x, const T &y) { if(x < y) x = y; }
template <class T>
inline void chmin(T &x, const T &y) { if(x > y) x = y; }
#define mp make_pair
#define fi first
#define se second
#define pc putchar
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define ppc __builtin_popcount
#define ctz __builtin_ctz
#define all(a) a.begin(), a.end()
#define clr(a, n) memset(a, 0, sizeof(a[0]) * (n + 1))
#define rep(i, l, r) for(int i = l, i##end = r; i <= i##end; ++ i)
#define per(i, r, l) for(int i = r, i##end = l; i >= i##end; -- i)
#define fsub(T, S) for(int T = S, T##_f = T; T; T = (T - 1) & T##_f)
#define fsubm(T, S) for(int T = S, T##_f = T; T; T = (T - 1) & T##_f) if(T & (T##_f & -T##_f))
#define Sin(S, i) ((S) >> (i) & 1)

char inputbuf[1 << 23], *p1 = inputbuf, *p2 = inputbuf;
//#define getchar() (p1 == p2 && (p2 = (p1 = inputbuf) + fread(inputbuf, 1, 1 << 23, stdin), p1 == p2) ? EOF : *p1++)
inline int read() {
	int res = 0; char ch = getchar(); bool f = true;
	for(; ch < '0' || ch > '9'; ch = getchar())
		f &= ch != '-';
	for(; ch >= '0' && ch <= '9'; ch = getchar())
		res = res * 10 + (ch ^ 48);
	return f ? res : -res;
}

const int N = 1e7 + 15, P = 1e9 + 7;

ll fac[N], ifac[N], pk[N];
int pr[N], pcnt;
int n, m;
bool npr[N];

ll poww(ll x, ll y = P - 2) {
	ll res = 1;
	for(; y; y >>= 1, x = x * x % P)
		if(y & 1) res = res * x % P;
	return res;
}

bool _v;

void init(int n) {
	fac[0] = 1;
	rep(i, 1, n) fac[i] = fac[i - 1] * i % P;
	ifac[n] = poww(fac[n]);
	per(i, n, 1) ifac[i - 1] = ifac[i] * i % P;
}

void prime(int n, int k) {
	npr[1] = 1;
	pk[1] = 1;
	rep(i, 2, n) {
		if(!npr[i]) pr[++ pcnt] = i, pk[i] = poww(i, k);
		for(int j = 1; j <= pcnt && pr[j] * i <= n; ++ j) {
			npr[pr[j] * i] = 1;
			pk[pr[j] * i] = pk[pr[j]] * pk[i] % P;
			if(i % pr[j] == 0) break;
		}
	}
}

signed main() {
	//clock_t _st = clock();
	//cerr << abs(&_u - &_v) / 1048576.0 << " MB" << endl;
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	scanf("%d", &n);
	m = n * 2;
	init(m);
	prime(n, m + 1);
	ll ans = 0, tmp;
	rep(i, 0, n - 1) {
		tmp = ifac[i] * ifac[m - i] % P * pk[n - i] % P;
		ans += i & 1 ? P - tmp : tmp;
	}
	ans = ans % P * poww(m + 1) * 2 % P;
	printf("%lld\n", ans);
	//cerr << (clock() - _st) * 1.0 / CLOCKS_PER_SEC << " s" << endl;
	return 0;
}

详细

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 0ms
memory: 12136kb

input:

1

output:

333333336

result:

ok 1 number(s): "333333336"

Test #2:

score: 0
Accepted
time: 2ms
memory: 11976kb

input:

2

output:

266666669

result:

ok 1 number(s): "266666669"

Test #3:

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

input:

3

output:

769047625

result:

ok 1 number(s): "769047625"

Subtask #2:

score: 10
Accepted

Test #4:

score: 10
Accepted
time: 1ms
memory: 12048kb

input:

4

output:

877865968

result:

ok 1 number(s): "877865968"

Test #5:

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

input:

5

output:

733342859

result:

ok 1 number(s): "733342859"

Test #6:

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

input:

6

output:

655899114

result:

ok 1 number(s): "655899114"

Test #7:

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

input:

7

output:

946326757

result:

ok 1 number(s): "946326757"

Test #8:

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

input:

8

output:

230714822

result:

ok 1 number(s): "230714822"

Test #9:

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

input:

9

output:

782967541

result:

ok 1 number(s): "782967541"

Test #10:

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

input:

10

output:

732371611

result:

ok 1 number(s): "732371611"

Subtask #3:

score: 10
Accepted

Test #11:

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

input:

15

output:

677123472

result:

ok 1 number(s): "677123472"

Test #12:

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

input:

13

output:

168974634

result:

ok 1 number(s): "168974634"

Test #13:

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

input:

26

output:

213343876

result:

ok 1 number(s): "213343876"

Test #14:

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

input:

29

output:

631124616

result:

ok 1 number(s): "631124616"

Subtask #4:

score: 15
Accepted

Test #15:

score: 15
Accepted
time: 1ms
memory: 12056kb

input:

37

output:

349256161

result:

ok 1 number(s): "349256161"

Test #16:

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

input:

104

output:

351095881

result:

ok 1 number(s): "351095881"

Test #17:

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

input:

194

output:

895504391

result:

ok 1 number(s): "895504391"

Test #18:

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

input:

197

output:

923555376

result:

ok 1 number(s): "923555376"

Test #19:

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

input:

198

output:

512220517

result:

ok 1 number(s): "512220517"

Subtask #5:

score: 15
Accepted

Test #20:

score: 15
Accepted
time: 0ms
memory: 12056kb

input:

562

output:

255062346

result:

ok 1 number(s): "255062346"

Test #21:

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

input:

1007

output:

735041605

result:

ok 1 number(s): "735041605"

Test #22:

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

input:

1788

output:

208261384

result:

ok 1 number(s): "208261384"

Test #23:

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

input:

1980

output:

875427987

result:

ok 1 number(s): "875427987"

Test #24:

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

input:

1983

output:

571776252

result:

ok 1 number(s): "571776252"

Test #25:

score: 0
Accepted
time: 2ms
memory: 12136kb

input:

1992

output:

12983695

result:

ok 1 number(s): "12983695"

Subtask #6:

score: 15
Accepted

Test #26:

score: 15
Accepted
time: 0ms
memory: 12068kb

input:

3946

output:

977435333

result:

ok 1 number(s): "977435333"

Test #27:

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

input:

65944

output:

312666196

result:

ok 1 number(s): "312666196"

Test #28:

score: 0
Accepted
time: 3ms
memory: 16236kb

input:

163815

output:

163767254

result:

ok 1 number(s): "163767254"

Test #29:

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

input:

198732

output:

911833524

result:

ok 1 number(s): "911833524"

Test #30:

score: 0
Accepted
time: 3ms
memory: 18312kb

input:

199287

output:

910277128

result:

ok 1 number(s): "910277128"

Test #31:

score: 0
Accepted
time: 8ms
memory: 22488kb

input:

199819

output:

561747634

result:

ok 1 number(s): "561747634"

Subtask #7:

score: 30
Accepted

Test #32:

score: 30
Accepted
time: 8ms
memory: 22528kb

input:

315618

output:

602805814

result:

ok 1 number(s): "602805814"

Test #33:

score: 0
Accepted
time: 37ms
memory: 60004kb

input:

1130465

output:

898203793

result:

ok 1 number(s): "898203793"

Test #34:

score: 0
Accepted
time: 131ms
memory: 188296kb

input:

4399723

output:

101317224

result:

ok 1 number(s): "101317224"

Test #35:

score: 0
Accepted
time: 142ms
memory: 201920kb

input:

4804460

output:

114947085

result:

ok 1 number(s): "114947085"

Test #36:

score: 0
Accepted
time: 149ms
memory: 208012kb

input:

4995726

output:

460040939

result:

ok 1 number(s): "460040939"

Test #37:

score: 0
Accepted
time: 155ms
memory: 209784kb

input:

4999919

output:

780785591

result:

ok 1 number(s): "780785591"

Test #38:

score: 0
Accepted
time: 168ms
memory: 213856kb

input:

4999999

output:

742624725

result:

ok 1 number(s): "742624725"