oj.uz

Submission #966714

# Submission time Handle Problem Language Result Execution time Memory
966714 2024-04-20T08:49:56 Z manizare Party (INOI20_party) C++14
23 / 100
 334 ms 81816 KB 
#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 int 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 int maxn = 1e7+10 + 10,  inf = 1e9+10 , mod = 1e9 + 7 ;
int a2[maxn] , dp[70][70][130] , pr[140] ;

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

}

void f(int p = 1){
    if(p > N)return ;
    int x= p , k =0 ;
    while(x*2 <= N){
        k++;
        x*=2 ;
    }
    if((x+(1ll<<k)-1) <= N){
        pr[0] = 0 ;
        rep(i , 1 ,130)pr[i] = pr[i-1] + d[i] ;
        rep(i , 0 , k){
            int sm = 0 ;
            rep(j , 0 , 120){
                int 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 <int> A = cal(p*2) ;
    vector <int> B = cal(p*2+1) ;

    int d2[140] , ls[140] ;
    rep(i , 0 , 130){
        d2[i] =0 ;
        ls[i] = d[i] ;
    }
    d2[1] = 1 ;
    rep(i , 1 , 130){
        d2[i] += d[i-1] ;
    }
    rep(i , 0 , sz(B)-1){
        d2[i+2] += B[i] ;
    }
    rep(i , 0 , 130){
        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 , 130)d[i] = ls[i] ;
    pr[0] = d[0] ;
    rep(i , 1, 130)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 , 2*k){
        if(i ==0){
            ans = (ans + po2((N-1)%(mod-1))-1)%mod ;
            continue ;
        }
        int 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)%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){
                int ans = ch(i , d , k) ;
                int 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 ;
            }
        }
    }
    int T ;
    cin >> T ;
    while(T--){
        rep(i ,0 , 120)d[i] =0 ;
        int n;
        cin >> n ;
        N = n ;
        ans =0 ;
        f();
        cout << ans * po(po(2,n)-1 , mod-2)%mod << "\n"; 
    }
    return 0 ;
}
/*


*/

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 81488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 81336 KB Output is correct
2 Correct 69 ms 81488 KB Output is correct
3 Correct 67 ms 81380 KB Output is correct
4 Correct 67 ms 81392 KB Output is correct
5 Correct 69 ms 81492 KB Output is correct
6 Correct 68 ms 81512 KB Output is correct
7 Correct 68 ms 81304 KB Output is correct
8 Correct 70 ms 81296 KB Output is correct
9 Correct 66 ms 81436 KB Output is correct
10 Correct 68 ms 81492 KB Output is correct
11 Correct 319 ms 81496 KB Output is correct
12 Correct 318 ms 81588 KB Output is correct
13 Correct 334 ms 81488 KB Output is correct
14 Correct 320 ms 81592 KB Output is correct
15 Correct 320 ms 81408 KB Output is correct
16 Correct 320 ms 81592 KB Output is correct
17 Correct 322 ms 81492 KB Output is correct
18 Correct 321 ms 81816 KB Output is correct
19 Correct 318 ms 81584 KB Output is correct
20 Correct 323 ms 81788 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 255 ms 81488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 81488 KB Output isn't correct
2 Halted 0 ms 0 KB -