Submission #1003112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003112		vjudge1	Party (INOI20_party)	C++17	7 / 100	54 ms	17876 KiB

Main

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