oj.uz

Submission #469512

# Submission time Handle Problem Language Result Execution time Memory
469512 2021-09-01T08:33:53 Z radal Party (INOI20_party) C++14
0 / 100
 806 ms 1188 KB 
#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,ll k){
    ll ans = 1;
    rep(i,0,61){
        ans = ans*ans%mod;
        if (k&(1 << i))
            ans = ans*n%mod;
    }
    return ans;
    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>,ll> 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,261)
        pw[i] = 2*pw[i-1]%mod;
    while (q--){
        cin >> n;
        if (__builtin_popcountll(n+1) == 1){
            cnt1.clear();
            cn1.clear();
            int z = 0;
            for (ll i = (n+1)/2; i >= 1; i >>= 1){
                z++;
                cnt1[{i,0}] = 1;
                rep(j,1,z){
                    if (z > 1)
                        cnt1[{i,j}] = cnt1[{2*i,j-1}]*2;
                }
            }
            for (ll i = 2; i < n; i <<= 1){
                cn1[{i,1}] = 1;
                rep(j,2,121)
                    cn1[{i,j}] = cn1[{i/2,j-1}]+cnt1[{i,j-2}];
            }
            ll ans = 0,y = poww(2,n)-1;
            y = poww(y,mod-2);
            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;
                    ll g = poww(2,x+y)-1,r = poww(2,n-sm);
                    ans = mkay(ans,j*g%mod*r%mod*(i%mod)%mod);
                }
            }
            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;
    }
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 806 ms 1188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 1100 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 716 KB Output isn't correct
2 Halted 0 ms 0 KB -