Submission #469498

#	Time	Username	Problem	Language	Result	Execution time	Memory
469498		radal	Party (INOI20_party)	C++14	7 / 100	659 ms	1100 KiB

Main

#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;
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 33
• Subtask 4: 0 / 37