Submission #623302

#	Time	Username	Problem	Language	Result	Execution time	Memory
623302		Arinoor	Party (INOI20_party)	C++17	7 / 100	3071 ms	7024 KiB

Main

#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 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 33
• Subtask 4: 0 / 37