oj.uz

Submission #1003409

# Submission time Handle Problem Language Result Execution time Memory
1003409 2024-06-20T09:56:36 Z vjudge1 Party (INOI20_party) C++17
7 / 100
 290 ms 604 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], n;
ll freq[120];
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 dfs(ll v, ll par = 0, ll depth = 0)
{
    freq[depth]++;
    for (ll to : {v >> 1, v * 2, v * 2 + 1}) if (to != par and to <= n and to >= 1) dfs(to, v, depth + 1);
}
void solve()
{
    cin >> n;
    if (n <= 200){
    ll ans = 0;
    for (ll i = 1; i <= n; i++)
    {
        for (ll j = 0; j < 20; j++) freq[j] = 0;
        dfs(i);
        ll cur = 0;
        for (ll j = 19; j >= 0; j--)
            ans = (ans + binpow(2, cur) * (binpow(2, freq[j]) - 1) % mod * j % mod) % mod, cur += freq[j];
    }
    ans = ans * inv(binpow(2, n) - 1 + mod) % mod;
    cout << ans << endl;
        
    }
    else
    {
        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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 6 ms 348 KB Output is correct
3 Correct 5 ms 472 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 6 ms 348 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 6 ms 348 KB Output is correct
8 Correct 6 ms 348 KB Output is correct
9 Correct 5 ms 348 KB Output is correct
10 Correct 9 ms 476 KB Output is correct
11 Correct 268 ms 604 KB Output is correct
12 Correct 256 ms 472 KB Output is correct
13 Correct 290 ms 344 KB Output is correct
14 Correct 235 ms 344 KB Output is correct
15 Correct 267 ms 456 KB Output is correct
16 Correct 237 ms 344 KB Output is correct
17 Correct 159 ms 468 KB Output is correct
18 Correct 148 ms 344 KB Output is correct
19 Correct 153 ms 348 KB Output is correct
20 Correct 151 ms 476 KB Output is correct

Subtask #2
0 / 23.0

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

Subtask #3
0 / 33.0

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

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 6 ms 348 KB Output is correct
3 Correct 5 ms 472 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 6 ms 348 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 6 ms 348 KB Output is correct
8 Correct 6 ms 348 KB Output is correct
9 Correct 5 ms 348 KB Output is correct
10 Correct 9 ms 476 KB Output is correct
11 Correct 268 ms 604 KB Output is correct
12 Correct 256 ms 472 KB Output is correct
13 Correct 290 ms 344 KB Output is correct
14 Correct 235 ms 344 KB Output is correct
15 Correct 267 ms 456 KB Output is correct
16 Correct 237 ms 344 KB Output is correct
17 Correct 159 ms 468 KB Output is correct
18 Correct 148 ms 344 KB Output is correct
19 Correct 153 ms 348 KB Output is correct
20 Correct 151 ms 476 KB Output is correct
21 Incorrect 61 ms 348 KB Output isn't correct
22 Halted 0 ms 0 KB -