oj.uz

Submission #966657

# Submission time Handle Problem Language Result Execution time Memory
966657 2024-04-20T07:48:25 Z manizare Party (INOI20_party) C++14
23 / 100
 325 ms 83796 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] ;

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] ; 
void f(int n , int p = 1){
    int x= p , k =0 ;
    while(x*2 <= N){
        k++;
        x*=2 ;
    }
    if((x+(1ll<<k)-1) <= N){
        rep(i , 0 , k){
            int sm = 0 ;
            rep(j , 0 , 2*k){
                int t = dp[k][i][j] + (j >= i ? d[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 ;
    }

}

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 , 2*k+2){
                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(n);
        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 71 ms 83536 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 59 ms 83448 KB Output is correct
2 Correct 61 ms 83492 KB Output is correct
3 Correct 60 ms 83476 KB Output is correct
4 Correct 59 ms 83536 KB Output is correct
5 Correct 59 ms 83544 KB Output is correct
6 Correct 59 ms 83516 KB Output is correct
7 Correct 57 ms 83428 KB Output is correct
8 Correct 58 ms 83468 KB Output is correct
9 Correct 58 ms 83476 KB Output is correct
10 Correct 58 ms 83284 KB Output is correct
11 Correct 305 ms 83760 KB Output is correct
12 Correct 303 ms 83556 KB Output is correct
13 Correct 309 ms 83544 KB Output is correct
14 Correct 318 ms 83544 KB Output is correct
15 Correct 325 ms 83552 KB Output is correct
16 Correct 307 ms 83536 KB Output is correct
17 Correct 313 ms 83796 KB Output is correct
18 Correct 302 ms 83516 KB Output is correct
19 Correct 302 ms 83560 KB Output is correct
20 Correct 306 ms 83552 KB Output is correct

Subtask #3
0 / 33.0

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

Subtask #4
0 / 37.0

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