#include <bits/stdc++.h>
#pragma GCC target ("avx,avx2,fma")
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
#define X first
#define Y second
#define debug(x) cerr << #x << ": " << x << endl;
#define endl '\n'
#define pb push_back
#define rep(i,l,r) for (int i=l; i<r; i++)
#define repr(i,r,l) for (int i=r; i>=l; i--)
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const long long int N = 1e3+20,mod = 1e9+7,inf=1e9+1;
ll poww(int n,int k){
if (!k) return 1;
if (k == 1) return n;
ll r = poww(n,k/2);
return (r*r%mod)*poww(n,(k&1))%mod;
}
ll cnt[N][20],n,cn[N][20],pw[N];
map<pair<ll,int>,int> cnt1,cn1;
void dfs(int v){
cnt[v][0] = 1;
if (2*v <= n){
dfs(2*v);
rep(i,1,20) cnt[v][i] = cnt[2*v][i-1];
}
if (2*v+1 <= n){
dfs(2*v+1);
rep(i,1,20) cnt[v][i] += cnt[2*v+1][i-1];
}
}
void dfs2(int v){
if (2*v <= n){
cn[2*v][1] = 1;
rep(i,2,20) cn[2*v][i] = cn[v][i-1]+cnt[v][i-1]-cnt[2*v][i-2];
dfs2(2*v);
}
if (2*v+1 <= n){
cn[2*v+1][1] = 1;
rep(i,2,20) cn[2*v+1][i] = cn[v][i-1]+cnt[v][i-1]-cnt[2*v+1][i-2];
dfs2(2*v+1);
}
}
inline int mkay(int a,int b){
if (a+b < mod) return a+b;
return a+b-mod;
}
int main(){
ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
int q;
cin >> q;
pw[0] = 1;
rep(i,1,201)
pw[i] = 2*pw[i-1]%mod;
while (q--){
memset(cnt,0,sizeof cnt);
memset(cn,0,sizeof cn);
cin >> n;
if (__builtin_popcount(n+1) == 1){
cnt1.clear();
cn1.clear();
ll z = 0;
for (ll i = (n+1)/2; i >= 1; i/=2){
z++;
cnt1[{i,0}] = 1;
rep(j,1,z){
if (z > 1)
cnt1[{i,j}] = cnt1[{2*i,j-1}]*2%mod;
}
}
for (ll i = 2; i < n; i <<= 1){
cn1[{i,1}] = 1;
rep(j,2,121)
cn1[{i,j}] = mkay(cn1[{i/2,j-1}],cnt1[{i,j-2}]);
}
ll ans = 0,y = poww(2,n%mod)-1;
y = poww(y,mod-2);
z = 1;
/* for (ll i = 1; i < n; i *= 2){
ll sm = 1;
rep(j,1,121){
ll x = cnt1[{i,j}];
ll y = cn1[{i,j}];
sm += x+y;
ans = mkay(ans,j*(poww(2,mkay(y,x))-1)%mod*poww(2,(n-sm)%mod)%mod*z%mod);
}
z *= 2;
}*/
cout << ans*y%mod << endl;
continue;
}
memset(cn,0,sizeof cn);
memset(cnt,0,sizeof cnt);
dfs(1);
dfs2(1);
ll ans = 0,y = (pw[n]-1);
y = poww(y,mod-2);
rep(i,1,n+1){
int sm = 0;
rep(j,0,20){
sm += cnt[i][j]+cn[i][j];
ans = mkay(ans,(1ll*j*(pw[cnt[i][j]+cn[i][j]]-1)%mod)*pw[n-sm]%mod);
}
}
//cout << ans << endl;
cout << 1ll*ans*y%mod << endl;
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
2 ms |
1100 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
1100 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
