This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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, lg;
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 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 pwr(2, max(0, h - H - 1));
if(!check(h, H))
return 0;
return pwr(2, h - H - 1);
}
int main(){
ios;
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 ans = 0;
for(int h = 0; h <= lg; h ++){
for(int H = 0; H <= h; H ++){
int res = 0;
ll sum = 0;
for(int l = 0; l <= 2 * lg; l ++){
sum += dp[l][h][H];
int res2 = neg(pwr(2, dp[l][h][H] % (mod - 1)), 1);
res2 = mul(res2, pwr(2, (n - sum) % (mod - 1)));
res = add(res, mul(res2, l));
}
ans = add(ans, mul(res, get_cnt(h, H)));
}
}
int inv = pwr(neg(pwr(2, n % (mod - 1)), 1), mod - 2);
cout << mul(ans, inv) << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |