Submission #966730

#	Time	Username	Problem	Language	Result	Execution time	Memory
966730		manizare	Party (INOI20_party)	C++17	100 / 100	1717 ms	395340 KiB

Main

#include <bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define ld long double
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define ll long long 
#define PII pair<pii , pii>
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
#define deb(x) cout <<#x << " : " << x << "\n" ;
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll maxn = 5e7+10 + 10,  inf = 1e9+10 , mod = 1e9 + 7 ;
ll a2[maxn] , dp[70][70][130] , pr[140] ;

ll po2(int b){
    if(b==0)return 1 ;
    if(b < maxn)return a2[b]; 
    ll v =po2(b/2); 
    v=v *v % mod ;
    if(b&1) v= v*2% mod;
    return v; 
}
ll po(ll a,ll b){
    if(b==0)return 1 ;
    ll v =po(a,b/2); 
    v=v *v % mod ;
    if(b&1) v= v*a % mod;
    return v; 
}
ll ch(ll x ,ll d , ll k){
    if(d==-1)return 0;
    d = min(d , k-x);
    return ((1ll<<(d+1))-1);
}
ll ans =0 , N , d[130] ;
vector <ll> cal(ll p){
    ll x = p , k= 0 ;
    vector <ll> h; 
    while(x*2 <= N){
        x *= 2 ;
        k++;
    }
    rep(i , 0 , k)h.pb((1ll<<i)) ;    
    if((x+(1ll<<k)-1) <= N){
        return h ;
    }
    ll az = (x+(1ll<<k)-1) - N ;
    h.back()-=az;
    return h ; 

}

void f(ll p = 1){
    if(p > N)return ;
    ll x= p , k =0 ;
    while(x*2 <= N){
        k++;
        x*=2 ;
    }
    if((x+(1ll<<k)-1) <= N){
        pr[0] = 0 ;
        rep(i , 1 ,120)pr[i] = pr[i-1] + d[i] ;
        rep(i , 0 , k){
            ll sm = 0 ;
            rep(j , 0 , 120){
                ll t = dp[k][i][j] + (j >= i ? pr[j-i] : 0); 
                if(t == N)break ;
                sm = (sm + po2((N-t)%(mod-1))-1);
                if(sm > mod)sm -= mod ;
            }
            sm += mod;
            if(sm > mod)sm-=mod;
            ans = (ans + sm*po2(i))%mod ;
        }
        return ;
    }
    vector <ll> A = cal(p*2) ;
    vector <ll> B = cal(p*2+1) ;
    ll d2[130] , ls[130] ;
    rep(i , 0 , 120){
        d2[i] =0 ;
        ls[i] = d[i] ;
    }
    d2[1] = 1 ;
    rep(i , 1 , 120){
        d2[i] += d[i-1] ;
    }
    rep(i , 0 , sz(B)-1){
        d2[i+2] += B[i] ;
    }
    rep(i , 0 , 120){
        swap(d[i] , d2[i]) ;
    }
    f(p*2) ;
    rep(i , 0 , sz(B)-1){
        d[i+2] -= B[i] ;
    }
    rep(i , 0 ,sz(A)-1){
        d[i+2] += A[i] ;
    }
    f(p*2+1); 
    rep(i , 0 , 120)d[i] = ls[i] ;
    pr[0] = d[0] ;
    rep(i , 1, 120)pr[i] = pr[i-1] + d[i] ;
    rep(i , 1 , sz(A)-1)A[i] += A[i-1] ;
    rep(i , 1, sz(B)-1)B[i] += B[i-1] ;
    rep(i , 0 , 120){
        if(i ==0){
            ans = (ans + po2((N-1)%(mod-1))-1);
            if(ans > mod)ans-=mod;
            continue ;
        }
        ll t = pr[i] + A[min(sz(A)-1 , i-1)] + B[min(sz(B)-1 , i-1)]+1 ;
        ans = (ans + po2((N-t)%(mod-1))-1);
        if(ans > mod)ans -= mod ;
    }
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
    a2[0] = 1;
    rep(i , 1 ,maxn-1){
        a2[i] = a2[i-1]*2%mod ;
    }
    rep(k , 0 , 60){
        rep(i , 0 , k){
            rep(d , 0 , 120){
                ll ans = ch(i , d , k) ;
                ll x = i-1 , D = d-1 ;
                while(x!=-1 && D!=-1){
                    ans++ ;
                    ans = (ans + ch(x+1 , D-1 , k));
                    D--;
                    x--;
                }
                dp[k][i][d] = ans ;
            }
        }
    }
    map <ll,ll> mp ;
    int T ;
    cin >> T ;
    while(T--){
        rep(i ,0 , 120)d[i] =0 ;
        ll n;
        cin >> n ;
        if(mp[n]!=0){
            cout << mp[n] << "\n";
            continue ;
        }
        N = n ;
        ans =0 ;
        f();
        mp[n] = ans * po(po(2,n)-1 , mod-2)%mod;
        cout << ans * po(po(2,n)-1 , mod-2)%mod << "\n"; 
    }
    return 0 ;
}
/*


*/

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