526互联

CF1905E One-X

发布时间 2024-01-04 17:11:46作者: Luxinze
map<ll, pll> mp;

pll calc(ll n) {
	if(mp.find(n) != mp.end()) return mp[n];
	auto [lk, lb] = calc((n + 1) / 2); 
	auto [rk, rb] = calc(n / 2);
	ll t = (q_pow(2, (n + 1) / 2) - 1) * (q_pow(2, n / 2) - 1) % P;
	ll k = (t + 2 * lk + 2 * rk) % P;
	ll b = (lb + rk + rb) % P;
	/*
	  f[n][id] = t * id + f[ls][lsid] + f[rs][rsid]
	 */
	return mp[n] = {k % P, b % P};
}

void solve() {
	ll n;
	cin >> n;
	auto [k, b] = calc(n);
	cout << (k + b) % P << '\n';
}

int main() {
	int T; cin >> T;
	mp[1] = {1, 0};
	while(T --) solve();
	return 0;
}