oj.uz

Submission #623374

# Submission time Handle Problem Language Result Execution time Memory
623374 2022-08-05T14:05:17 Z Arinoor Party (INOI20_party) C++17
40 / 100
 3000 ms 3720 KB 
#include <bits/stdc++.h>
using namespace std;

#define ios				ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define pb				push_back
#define mp				make_pair
#define fi				first
#define se				second
#define all(x)			x.begin(), x.end()
#define bug(x)			cout << #x << " : " << x << '\n'

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 60;
const int mod = 1e9 + 7;
const int inf = 1e9 + 10;

ll n;
int dp[maxn << 1][maxn][maxn], pd[maxn << 1][maxn][maxn], pw[maxn], lg;

inline int add(int a, int b){
	int c = a + b;
	if(c >= mod) c -= mod;
	return c;
}

inline int neg(int a, int b){
	int c = a - b;
	if(c < 0) c += mod;
	return c;
}

inline int mul(int a, int b){
	return 1ll * a * b % mod;
}

inline int pwr(int a, int b){
	int res = 1;
	for(; b; b >>= 1, a = mul(a, a)) if(b & 1) res = mul(res, a);
	return res;
}

inline bool check(int h, int H){
	if(h > lg)
		return false;
	if(h < lg or H == lg)
		return true;
	return n >> (lg - (H + 1)) & 1;
}

inline int get_cnt(int h, int H){
	if(h > lg)
		return 0;
	if(h < lg or H == lg)
		return pw[max(0, h - H - 1)];
	if(!check(h, H))
		return 0;
	return pw[h - H - 1];
}

int main(){
	ios;
	pw[0] = 1;
	for(int i = 1; i < maxn; i ++)
		pw[i] = add(pw[i - 1], pw[i - 1]);
	int q; cin >> q;
	while(q--){
		cin >> n;
		if(n == 1){
			cout << "0\n";
			continue;
		}
		lg = 63 - __builtin_clzll(n);
		int inv = pwr(2, mod - 2);
		for(int h = 0; h <= lg; h ++){
			for(int H = 0; H <= h; H ++){
				dp[0][h][H] = pd[0][h][H] = dp[1][h][H] = pd[1][h][H] = 1;
				if(check(h, H)){
					dp[0][h][H] = 2;
					pd[0][h][H] = inv;
					int cnt = 0;
					if(H < h){
						cnt = 2 * check(h + 1, H) + 1;
					}
					else{
						cnt = check(h + 1, H) + check(h + 1, H + 1) + (h > 0);
					}
					dp[1][h][H] = pwr(2, cnt);
					pd[1][h][H] = pwr(inv, cnt);
				}
			}
		}
		for(int l = 2; l <= lg * 2; l ++){
			for(int h = 0; h <= lg; h ++){
				for(int H = 0; H <= h; H ++){
					int &r1 = dp[l][h][H];
					int &r2 = pd[l][h][H];
					r1 = r2 = 1;
					if(!check(h, H))
						continue;
					int cnt;
					if(H < h){
						if(h < lg){
							r1 = mul(dp[l - 1][h + 1][H], dp[l - 1][h + 1][H]);
							r2 = mul(pd[l - 1][h + 1][H], pd[l - 1][h + 1][H]);
						}
						r1 = mul(r1, dp[l - 1][h - 1][H]);
						r2 = mul(r2, pd[l - 1][h - 1][H]);
						cnt = 2 * check(h + 1, H) + 1;
					}
					else{
						if(h < lg){
							r1 = mul(dp[l - 1][h + 1][H], dp[l - 1][h + 1][H + 1]);
							r2 = mul(pd[l - 1][h + 1][H], pd[l - 1][h + 1][H + 1]);
						}
						if(h){
							r1 = mul(r1, dp[l - 1][h - 1][H - 1]);
							r2 = mul(r2, pd[l - 1][h - 1][H - 1]);
						}
						cnt = check(h + 1, H + 1) + check(h + 1, H) + (h > 0);
					}
					if(l > 2) cnt --;
					r1 = mul(r1, pwr(pd[l - 2][h][H], cnt));
					r2 = mul(r2, pwr(dp[l - 2][h][H], cnt));
				}
			}
		}
		int ans = 0;
		int tot = pwr(2, n % (mod - 1));
		for(int h = 0; h <= lg; h ++){
			for(int H = 0; H <= h; H ++){
				int res = 0;
				int p = tot;
				for(int l = 0; l <= 2 * lg; l ++){
					p = mul(p, pd[l][h][H]);
					int cnt = mul(neg(dp[l][h][H], 1), p);
					res = add(res, mul(cnt, l));
				}
				ans = add(ans, mul(res, get_cnt(h, H)));
			}
		}
		inv = pwr(neg(tot, 1), mod - 2);
		cout << mul(ans, inv) << '\n';
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 452 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 452 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 24 ms 468 KB Output is correct
12 Correct 28 ms 468 KB Output is correct
13 Correct 24 ms 460 KB Output is correct
14 Correct 23 ms 456 KB Output is correct
15 Correct 23 ms 476 KB Output is correct
16 Correct 22 ms 480 KB Output is correct
17 Correct 23 ms 484 KB Output is correct
18 Correct 22 ms 468 KB Output is correct
19 Correct 22 ms 476 KB Output is correct
20 Correct 23 ms 468 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 3608 KB Output is correct
2 Correct 426 ms 3672 KB Output is correct
3 Correct 418 ms 3604 KB Output is correct
4 Correct 325 ms 3496 KB Output is correct
5 Correct 410 ms 3608 KB Output is correct
6 Correct 386 ms 3612 KB Output is correct
7 Correct 361 ms 3520 KB Output is correct
8 Correct 384 ms 3652 KB Output is correct
9 Correct 353 ms 3608 KB Output is correct
10 Correct 457 ms 3644 KB Output is correct
11 Execution timed out 3060 ms 3640 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 3532 KB Output is correct
2 Correct 403 ms 3608 KB Output is correct
3 Correct 347 ms 3604 KB Output is correct
4 Correct 360 ms 3604 KB Output is correct
5 Correct 416 ms 3664 KB Output is correct
6 Correct 404 ms 3668 KB Output is correct
7 Correct 388 ms 3640 KB Output is correct
8 Correct 409 ms 3668 KB Output is correct
9 Correct 367 ms 3600 KB Output is correct
10 Correct 389 ms 3708 KB Output is correct
11 Correct 1430 ms 3608 KB Output is correct
12 Correct 1495 ms 3608 KB Output is correct
13 Correct 1441 ms 3612 KB Output is correct
14 Correct 1458 ms 3628 KB Output is correct
15 Correct 1459 ms 3612 KB Output is correct
16 Correct 1467 ms 3616 KB Output is correct
17 Correct 1455 ms 3612 KB Output is correct
18 Correct 1423 ms 3612 KB Output is correct
19 Correct 1454 ms 3720 KB Output is correct
20 Correct 1411 ms 3612 KB Output is correct

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 452 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 452 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 24 ms 468 KB Output is correct
12 Correct 28 ms 468 KB Output is correct
13 Correct 24 ms 460 KB Output is correct
14 Correct 23 ms 456 KB Output is correct
15 Correct 23 ms 476 KB Output is correct
16 Correct 22 ms 480 KB Output is correct
17 Correct 23 ms 484 KB Output is correct
18 Correct 22 ms 468 KB Output is correct
19 Correct 22 ms 476 KB Output is correct
20 Correct 23 ms 468 KB Output is correct
21 Correct 425 ms 3608 KB Output is correct
22 Correct 426 ms 3672 KB Output is correct
23 Correct 418 ms 3604 KB Output is correct
24 Correct 325 ms 3496 KB Output is correct
25 Correct 410 ms 3608 KB Output is correct
26 Correct 386 ms 3612 KB Output is correct
27 Correct 361 ms 3520 KB Output is correct
28 Correct 384 ms 3652 KB Output is correct
29 Correct 353 ms 3608 KB Output is correct
30 Correct 457 ms 3644 KB Output is correct
31 Execution timed out 3060 ms 3640 KB Time limit exceeded
32 Halted 0 ms 0 KB -