oj.uz

Submission #623302

# Submission time Handle Problem Language Result Execution time Memory
623302 2022-08-05T12:28:17 Z Arinoor Party (INOI20_party) C++17
7 / 100
 3000 ms 7024 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 = 61;
const int mod = 1e9 + 7;
const int inf = 1e9 + 10;

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

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 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 pwr[max(0, h - H - 1)];
	if(!check(h, H))
		return 0;
	return pwr[h - H - 1];
}

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

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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 468 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 592 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 34 ms 556 KB Output is correct
12 Correct 33 ms 468 KB Output is correct
13 Correct 34 ms 556 KB Output is correct
14 Correct 33 ms 548 KB Output is correct
15 Correct 35 ms 464 KB Output is correct
16 Correct 35 ms 536 KB Output is correct
17 Correct 38 ms 468 KB Output is correct
18 Correct 31 ms 548 KB Output is correct
19 Correct 31 ms 468 KB Output is correct
20 Correct 30 ms 464 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3071 ms 7020 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3061 ms 7024 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 468 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 592 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 34 ms 556 KB Output is correct
12 Correct 33 ms 468 KB Output is correct
13 Correct 34 ms 556 KB Output is correct
14 Correct 33 ms 548 KB Output is correct
15 Correct 35 ms 464 KB Output is correct
16 Correct 35 ms 536 KB Output is correct
17 Correct 38 ms 468 KB Output is correct
18 Correct 31 ms 548 KB Output is correct
19 Correct 31 ms 468 KB Output is correct
20 Correct 30 ms 464 KB Output is correct
21 Execution timed out 3071 ms 7020 KB Time limit exceeded
22 Halted 0 ms 0 KB -