oj.uz

Submission #1003107

# Submission time Handle Problem Language Result Execution time Memory
1003107 2024-06-20T06:14:47 Z vjudge1 Party (INOI20_party) C++17
0 / 100
 3000 ms 17756 KB 
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9+7;
const int N = 2100, LG=10;
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;
    for(int i = 1;i<=n;i++) {
      for(int j = 0;j<=n;j++) {
        long long pw1 = 1, pw2=1;
        int cnt=0;
        for(int k = 1;k<=n;k++) {
          if(dist[i][k] < j) {
            pw1=(pw1*binpow(2, mod-2, mod))%mod;
          }
          else if(dist[i][k] == j) {
            pw2=(pw2*binpow(2, mod-2, mod))%mod;
          }
        }
        ans+=((pw1*(1-pw2))%mod*j)%mod;
        ans%=mod;
        ans+=mod;
        ans%=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();
    }
  }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:60:13: warning: unused variable 'cnt' [-Wunused-variable]
   60 |         int cnt=0;
      |             ^~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2612 ms 17756 KB Output is correct
2 Execution timed out 3013 ms 17752 KB Time limit exceeded
3 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 Correct 2612 ms 17756 KB Output is correct
2 Execution timed out 3013 ms 17752 KB Time limit exceeded
3 Halted 0 ms 0 KB -