oj.uz

Submission #966654

# Submission time Handle Problem Language Result Execution time Memory
966654 2024-04-20T07:46:03 Z manizare Party (INOI20_party) C++14
23 / 100
 1845 ms 83832 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))-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 70 ms 83520 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 89 ms 83504 KB Output is correct
2 Correct 92 ms 83544 KB Output is correct
3 Correct 86 ms 83420 KB Output is correct
4 Correct 79 ms 83704 KB Output is correct
5 Correct 88 ms 83520 KB Output is correct
6 Correct 87 ms 83792 KB Output is correct
7 Correct 84 ms 83540 KB Output is correct
8 Correct 83 ms 83540 KB Output is correct
9 Correct 82 ms 83540 KB Output is correct
10 Correct 84 ms 83544 KB Output is correct
11 Correct 1842 ms 83596 KB Output is correct
12 Correct 1824 ms 83792 KB Output is correct
13 Correct 1842 ms 83756 KB Output is correct
14 Correct 1825 ms 83580 KB Output is correct
15 Correct 1829 ms 83812 KB Output is correct
16 Correct 1828 ms 83832 KB Output is correct
17 Correct 1845 ms 83596 KB Output is correct
18 Correct 1830 ms 83820 KB Output is correct
19 Correct 1833 ms 83600 KB Output is correct
20 Correct 1828 ms 83804 KB Output is correct

Subtask #3
0 / 33.0

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

Subtask #4
0 / 37.0

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