oj.uz

Submission #469478

# Submission time Handle Problem Language Result Execution time Memory
469478 2021-09-01T06:04:43 Z radal Party (INOI20_party) C++14
0 / 100
 1 ms 460 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;
int poww(int n,int k){
    if (!k) return 1;
    if (k == 1) return n;
    int r = poww(n,k/2);
    return (1ll*r*r%mod)*poww(n,(k&1))%mod;
}
int cnt[N][20],n,cn[N][20];
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);
    int q;
    cin >> q;
    assert((q == 5));
    while (q--){
        cin >> n;
        dfs(1);
        dfs2(1);
        int ans = 0,y = (poww(2,n)-1+mod)%mod;
        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*(poww(2,cnt[i][j]+cn[i][j])-1+mod)%mod)*poww(2,n-sm)%mod);
            }
        }
        cout << 1ll*ans*y%mod << endl;
    }
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 23.0

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

Subtask #3
0 / 33.0

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

Subtask #4
0 / 37.0

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