oj.uz

Submission #1003112

# Submission time Handle Problem Language Result Execution time Memory
1003112 2024-06-20T06:20:53 Z vjudge1 Party (INOI20_party) C++17
7 / 100
 54 ms 17876 KB 
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9+7;
const int N = 2100, lg=20;
long long binpow(long long a, long long b, long long MOD) {
  a%=MOD;
  long long res = 1;
  while(b) {
    if(b&1){ 
      res=(res*a)%MOD;
    }
    a=(a*a)%MOD;
    b>>=1ll;
  }
  res%=MOD;
  return res;
}
int dist[N][N];
int tmp;
vector<int> g[N];
void dfs(int at, int p=0) {
  for(int to:g[at]) {
    if(to == p)continue;
    dist[tmp][to] = dist[tmp][at]+1;
    dfs(to, at);
  }
}
long long res[N];
int main () {
  cin.tie(0)->sync_with_stdio(0);
  int q;
  cin >> q;
  memset(res, -1, sizeof res);
  while(q--) {
    int n;
    cin >> n;
    if(res[n] !=-1) {
      cout << res[n] << "\n";
      continue;
    }
    memset(dist, 0, sizeof dist);
    for(int i = 1;i<=n;i++) {
      if(2*i <= n) {
        g[i].push_back(2*i);
        g[2*i].push_back(i);
      }
      if(2*i+1 <=n) {
        g[i].push_back(2*i+1);
        g[2*i+1].push_back(i);
      }
    }
    for(int i = 1;i<=n;i++) {
      tmp = i;
      dfs(i, 0);
    }
    long long ans=0;
    int cnt[n+1][lg+1];
    memset(cnt, 0, sizeof cnt);
    for(int i = 1;i<=n;i++) {
      for(int k = 1;k<=n;k++) {
          cnt[i][dist[i][k]]++;
      }
    }
    for(int i = 1;i<=n;i++) {
      long long pw1 = 1;
      for(int j = 0;j<=min(n, lg);j++) {
        long long pw2 = binpow(binpow(2, cnt[i][j], mod), mod-2, mod);
        ans+=((pw1*(1-pw2))%mod*j)%mod;
        ans%=mod;
        ans+=mod;
        ans%=mod;
        pw1=(pw1*pw2)%mod;
      }
    }
    ans=(ans*binpow(2,n, mod))%mod;
    ans=(ans*binpow(binpow(2,n, mod)-1+mod, mod-2, mod))%mod;
    res[n] = ans;
    cout << ans << "\n";
    for(int i = 1;i<=n;i++) {
      g[i].clear();
    }
  }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 17756 KB Output is correct
2 Correct 54 ms 17876 KB Output is correct
3 Correct 51 ms 17756 KB Output is correct
4 Correct 44 ms 17756 KB Output is correct
5 Correct 11 ms 17752 KB Output is correct
6 Correct 12 ms 17756 KB Output is correct
7 Correct 10 ms 17752 KB Output is correct
8 Correct 11 ms 17792 KB Output is correct
9 Correct 10 ms 17756 KB Output is correct
10 Correct 11 ms 17756 KB Output is correct
11 Correct 7 ms 17744 KB Output is correct
12 Correct 7 ms 17756 KB Output is correct
13 Correct 10 ms 17756 KB Output is correct
14 Correct 7 ms 17756 KB Output is correct
15 Correct 7 ms 17816 KB Output is correct
16 Correct 7 ms 17756 KB Output is correct
17 Correct 7 ms 17780 KB Output is correct
18 Correct 8 ms 17752 KB Output is correct
19 Correct 7 ms 17756 KB Output is correct
20 Correct 8 ms 17788 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 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 Correct 45 ms 17756 KB Output is correct
2 Correct 54 ms 17876 KB Output is correct
3 Correct 51 ms 17756 KB Output is correct
4 Correct 44 ms 17756 KB Output is correct
5 Correct 11 ms 17752 KB Output is correct
6 Correct 12 ms 17756 KB Output is correct
7 Correct 10 ms 17752 KB Output is correct
8 Correct 11 ms 17792 KB Output is correct
9 Correct 10 ms 17756 KB Output is correct
10 Correct 11 ms 17756 KB Output is correct
11 Correct 7 ms 17744 KB Output is correct
12 Correct 7 ms 17756 KB Output is correct
13 Correct 10 ms 17756 KB Output is correct
14 Correct 7 ms 17756 KB Output is correct
15 Correct 7 ms 17816 KB Output is correct
16 Correct 7 ms 17756 KB Output is correct
17 Correct 7 ms 17780 KB Output is correct
18 Correct 8 ms 17752 KB Output is correct
19 Correct 7 ms 17756 KB Output is correct
20 Correct 8 ms 17788 KB Output is correct
21 Runtime error 1 ms 600 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -