제출 #623374

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
623374		Arinoor	Party (INOI20_party)	C++17	40 / 100	3060 ms	3720 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 = 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 / 7
• Subtask 2: 0 / 23
• Subtask 3: 33 / 33
• Subtask 4: 0 / 37