oj.uz

Submission #1032789

# Submission time Handle Problem Language Result Execution time Memory
1032789 2024-07-24T08:42:30 Z vjudge1 Party (INOI20_party) C++17
0 / 100
 6 ms 604 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 201, mod = 1e9+7;

int q, n, ans, dis[N], cnt[N];

int pw(int x, int y) {
  return (!y ? 1 : pw(x*x % mod, y >> 1) * (y & 1 ? x : 1) % mod);
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> q;
  for (int i = 0; i < q; i++) {
    cin >> n;
    
    ans = 0;
    for (int i = 1; i <= n; i++) {
      memset(dis, -1, sizeof(dis));
      memset(cnt, 0, sizeof(cnt));

      queue<pair<int, int>> q;
      q.push(make_pair(0, i));
      while (!q.empty()) {
        int d = q.front().first;
        int x = q.front().second;
        q.pop();

        if (dis[x] != -1) continue;
        dis[x] = d;
        cnt[d]++;

        if (x/2 >= 1 && dis[x/2] == -1) q.push(make_pair(d+1, x/2));
        if (x*2 <= n && dis[x*2] == -1) q.push(make_pair(d+1, x*2));
        if (x*2 + 1 <= n && dis[x*2 + 1] == -1) q.push(make_pair(d+1, x*2 + 1));
      }

      for (int j = n-1; j > 0; j--) {
        ans += j * ((pw(2, cnt[j]) - 1 + mod) % mod) % mod * pw(2, cnt[j+1]) % mod;
        cnt[j] += cnt[j+1];
      }
    }

    cout << ans * pw((pw(2, n) - 1 + mod) % mod, mod-2) % mod << "\n";
  }
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

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