oj.uz

Submission #623395

# Submission time Handle Problem Language Result Execution time Memory
623395 2022-08-05T14:15:11 Z Arinoor Party (INOI20_party) C++17
40 / 100
 3000 ms 3656 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 --;
					if(cnt == 2){
						r1 = mul(r1, mul(pd[l - 2][h][H], pd[l - 2][h][H]));
						r2 = mul(r2, mul(dp[l - 2][h][H], dp[l - 2][h][H]));
					}
					else if(cnt == 1){
						r1 = mul(r1, pd[l - 2][h][H]);
						r2 = mul(r2, dp[l - 2][h][H]);
					}
					else if(cnt == 3){
						r1 = mul(r1, pwr(pd[l - 2][h][H], 3));
						r2 = mul(r2, pwr(dp[l - 2][h][H], 3));
					}
				}
			}
		}
		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 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 18 ms 468 KB Output is correct
12 Correct 18 ms 484 KB Output is correct
13 Correct 18 ms 468 KB Output is correct
14 Correct 21 ms 480 KB Output is correct
15 Correct 20 ms 472 KB Output is correct
16 Correct 18 ms 480 KB Output is correct
17 Correct 18 ms 468 KB Output is correct
18 Correct 18 ms 468 KB Output is correct
19 Correct 19 ms 472 KB Output is correct
20 Correct 20 ms 484 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 3596 KB Output is correct
2 Correct 301 ms 3520 KB Output is correct
3 Correct 277 ms 3544 KB Output is correct
4 Correct 244 ms 3604 KB Output is correct
5 Correct 282 ms 3540 KB Output is correct
6 Correct 278 ms 3604 KB Output is correct
7 Correct 253 ms 3600 KB Output is correct
8 Correct 265 ms 3600 KB Output is correct
9 Correct 268 ms 3548 KB Output is correct
10 Correct 278 ms 3604 KB Output is correct
11 Execution timed out 3095 ms 3600 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 3656 KB Output is correct
2 Correct 286 ms 3540 KB Output is correct
3 Correct 260 ms 3624 KB Output is correct
4 Correct 284 ms 3596 KB Output is correct
5 Correct 322 ms 3656 KB Output is correct
6 Correct 303 ms 3600 KB Output is correct
7 Correct 292 ms 3656 KB Output is correct
8 Correct 322 ms 3656 KB Output is correct
9 Correct 363 ms 3596 KB Output is correct
10 Correct 311 ms 3604 KB Output is correct
11 Correct 1119 ms 3604 KB Output is correct
12 Correct 1366 ms 3600 KB Output is correct
13 Correct 1174 ms 3600 KB Output is correct
14 Correct 1050 ms 3620 KB Output is correct
15 Correct 1044 ms 3540 KB Output is correct
16 Correct 2674 ms 3532 KB Output is correct
17 Correct 1229 ms 3604 KB Output is correct
18 Correct 1932 ms 3604 KB Output is correct
19 Correct 1420 ms 3608 KB Output is correct
20 Correct 1100 ms 3604 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 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 18 ms 468 KB Output is correct
12 Correct 18 ms 484 KB Output is correct
13 Correct 18 ms 468 KB Output is correct
14 Correct 21 ms 480 KB Output is correct
15 Correct 20 ms 472 KB Output is correct
16 Correct 18 ms 480 KB Output is correct
17 Correct 18 ms 468 KB Output is correct
18 Correct 18 ms 468 KB Output is correct
19 Correct 19 ms 472 KB Output is correct
20 Correct 20 ms 484 KB Output is correct
21 Correct 262 ms 3596 KB Output is correct
22 Correct 301 ms 3520 KB Output is correct
23 Correct 277 ms 3544 KB Output is correct
24 Correct 244 ms 3604 KB Output is correct
25 Correct 282 ms 3540 KB Output is correct
26 Correct 278 ms 3604 KB Output is correct
27 Correct 253 ms 3600 KB Output is correct
28 Correct 265 ms 3600 KB Output is correct
29 Correct 268 ms 3548 KB Output is correct
30 Correct 278 ms 3604 KB Output is correct
31 Execution timed out 3095 ms 3600 KB Time limit exceeded
32 Halted 0 ms 0 KB -