Submission #469485

#	Time	Username	Problem	Language	Result	Execution time	Memory
469485		radal	Party (INOI20_party)	C++14	0 / 100	2 ms	460 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;
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],pw[N];
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 == 200));
    pw[0] = 1;
    rep(i,1,201)
        pw[i] = 2*pw[i-1]%mod;
    while (q--){
        cin >> n;
        dfs(1);
        dfs2(1);
        int ans = 0,y = (pw[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*(pw[cnt[i][j]+cn[i][j]]-1+mod)%mod)*pw[n-sm]%mod);
            }
        }
        cout << 1ll*ans*y%mod << endl;
    }
}

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