oj.uz

Submission #469513

# Submission time Handle Problem Language Result Execution time Memory
469513 2021-09-01T08:35:36 Z radal Party (INOI20_party) C++14
7 / 100
 3000 ms 1304 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;
    repr(i,60,0){
        ans = ans*ans%mod;
        if (k&(1ll << 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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 716 KB Output is correct
2 Correct 9 ms 724 KB Output is correct
3 Correct 11 ms 724 KB Output is correct
4 Correct 12 ms 728 KB Output is correct
5 Correct 4 ms 588 KB Output is correct
6 Correct 4 ms 588 KB Output is correct
7 Correct 4 ms 588 KB Output is correct
8 Correct 4 ms 588 KB Output is correct
9 Correct 80 ms 332 KB Output is correct
10 Correct 86 ms 332 KB Output is correct
11 Correct 1503 ms 424 KB Output is correct
12 Correct 1506 ms 452 KB Output is correct
13 Correct 67 ms 588 KB Output is correct
14 Correct 65 ms 640 KB Output is correct
15 Correct 67 ms 632 KB Output is correct
16 Correct 66 ms 632 KB Output is correct
17 Correct 56 ms 588 KB Output is correct
18 Correct 54 ms 640 KB Output is correct
19 Correct 57 ms 716 KB Output is correct
20 Correct 55 ms 636 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 800 ms 1188 KB Output is correct
2 Correct 854 ms 1220 KB Output is correct
3 Correct 797 ms 1292 KB Output is correct
4 Correct 769 ms 1304 KB Output is correct
5 Correct 806 ms 1188 KB Output is correct
6 Correct 808 ms 1196 KB Output is correct
7 Correct 745 ms 1212 KB Output is correct
8 Correct 813 ms 1096 KB Output is correct
9 Correct 790 ms 1120 KB Output is correct
10 Correct 806 ms 1220 KB Output is correct
11 Execution timed out 3066 ms 1184 KB Time limit exceeded
12 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 Correct 12 ms 716 KB Output is correct
2 Correct 9 ms 724 KB Output is correct
3 Correct 11 ms 724 KB Output is correct
4 Correct 12 ms 728 KB Output is correct
5 Correct 4 ms 588 KB Output is correct
6 Correct 4 ms 588 KB Output is correct
7 Correct 4 ms 588 KB Output is correct
8 Correct 4 ms 588 KB Output is correct
9 Correct 80 ms 332 KB Output is correct
10 Correct 86 ms 332 KB Output is correct
11 Correct 1503 ms 424 KB Output is correct
12 Correct 1506 ms 452 KB Output is correct
13 Correct 67 ms 588 KB Output is correct
14 Correct 65 ms 640 KB Output is correct
15 Correct 67 ms 632 KB Output is correct
16 Correct 66 ms 632 KB Output is correct
17 Correct 56 ms 588 KB Output is correct
18 Correct 54 ms 640 KB Output is correct
19 Correct 57 ms 716 KB Output is correct
20 Correct 55 ms 636 KB Output is correct
21 Correct 800 ms 1188 KB Output is correct
22 Correct 854 ms 1220 KB Output is correct
23 Correct 797 ms 1292 KB Output is correct
24 Correct 769 ms 1304 KB Output is correct
25 Correct 806 ms 1188 KB Output is correct
26 Correct 808 ms 1196 KB Output is correct
27 Correct 745 ms 1212 KB Output is correct
28 Correct 813 ms 1096 KB Output is correct
29 Correct 790 ms 1120 KB Output is correct
30 Correct 806 ms 1220 KB Output is correct
31 Execution timed out 3066 ms 1184 KB Time limit exceeded
32 Halted 0 ms 0 KB -