oj.uz

Submission #1003399

# Submission time Handle Problem Language Result Execution time Memory
1003399 2024-06-20T09:44:41 Z vjudge1 Party (INOI20_party) C++17
23 / 100
 2830 ms 8544 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define endl "\n"
 
using namespace std;
using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll mod = 1e9 + 7, N = 1e6 + 5;
ll pw[N];
void precomp()
{
    pw[0] = 1;
    for (ll i = 1; i < N; i++) pw[i] = pw[i - 1] * 2 % mod;
}
ll binpow(ll n, ll p)
{
    ll ans = 1;
    while (p)
    {
        ans = (p & 1 ? (ans * n) % mod : ans);
        n = (n * n) % mod;
        p >>= 1;
    }
    return ans;
}
ll pww(ll p)
{
    if (p < N) return pw[p];
    if (p & 1) 
    {
        p = pww(p >> 1);
        return p * p * 2 % mod;
    }
    p = pww(p >> 1);
    return p * p % mod;
}
ll inv(ll x)
{
    return binpow(x, mod - 2);
}
void solve()
{
    ll n;
    cin >> n;
    ll ans = 0, lg = __lg(n);
    ll freq[120];
    for (ll i = 0; i <= lg; i++)
    {
        ll res = 0;
        for (ll j = 0; j < 120; j++) freq[j] = 0;
        for (ll j = 1; j <= i; j++){
            freq[j]++;
            for (ll x = 1; i - j + x <= lg; x++) freq[j + x] += (1ll << (x - 1));
        }
        for (ll x = 1; x + i <= lg; x++) freq[x] += (1ll << x);
        ll cur = 0;
        for (ll j = 119; j >= 0; j--)
            res = (res + pww(cur) * (pww(freq[j]) - 1) % mod * j % mod) % mod, cur += freq[j];
        ans = (ans + binpow(2, i) * res % mod) % mod;
    }
    ans = ans * inv(binpow(2, n) - 1 + mod) % mod;
    cout << ans << endl;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    precomp();
    cin >> t;
    for (ll cs = 1; cs <= t; cs++)
        solve();
    // cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 8284 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 70 ms 8284 KB Output is correct
2 Correct 78 ms 8540 KB Output is correct
3 Correct 67 ms 8284 KB Output is correct
4 Correct 60 ms 8284 KB Output is correct
5 Correct 72 ms 8284 KB Output is correct
6 Correct 69 ms 8280 KB Output is correct
7 Correct 66 ms 8536 KB Output is correct
8 Correct 69 ms 8280 KB Output is correct
9 Correct 60 ms 8280 KB Output is correct
10 Correct 57 ms 8284 KB Output is correct
11 Correct 2567 ms 8284 KB Output is correct
12 Correct 2660 ms 8284 KB Output is correct
13 Correct 2651 ms 8544 KB Output is correct
14 Correct 2802 ms 8288 KB Output is correct
15 Correct 2830 ms 8280 KB Output is correct
16 Correct 2722 ms 8320 KB Output is correct
17 Correct 2723 ms 8280 KB Output is correct
18 Correct 2681 ms 8284 KB Output is correct
19 Correct 2813 ms 8328 KB Output is correct
20 Correct 2722 ms 8300 KB Output is correct

Subtask #3
0 / 33.0

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

Subtask #4
0 / 37.0

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