Submission #1032789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032789		vjudge1	Party (INOI20_party)	C++17	0 / 100	6 ms	604 KiB

Main

#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
• Subtask 2: 0 / 23
• Subtask 3: 0 / 33
• Subtask 4: 0 / 37