Submission #623321

#TimeUsernameProblemLanguageResultExecution timeMemory
623321ArinoorParty (INOI20_party)C++17
7 / 100
3088 ms7200 KiB
#include <bits/stdc++.h> using namespace std; #define ios ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0) #define pb push_back #define mp make_pair #define fi first #define se second #define all(x) x.begin(), x.end() #define bug(x) cout << #x << " : " << x << '\n' typedef long long ll; typedef pair<int, int> pii; const int maxn = 61; const int mod = 1e9 + 7; const int inf = 1e9 + 10; ll n, lg; ll dp[maxn << 1][maxn][maxn], pd[maxn << 1][maxn][maxn]; inline int add(int a, int b){ int c = a + b; if(c >= mod) c -= mod; return c; } inline int neg(int a, int b){ int c = a - b; if(c < 0) c += mod; return c; } inline int mul(int a, int b){ return 1ll * a * b % mod; } inline int pwr(int a, int b){ int res = 1; for(; b; b >>= 1, a = mul(a, a)) if(b & 1) res = mul(res, a); return res; } inline bool check(int h, int H){ if(h > lg) return false; if(h < lg or H == lg) return true; return n >> (lg - (H + 1)) & 1; } inline int get_cnt(int h, int H){ if(h > lg) return 0; if(h < lg or H == lg) return pwr(2, max(0, h - H - 1)); if(!check(h, H)) return 0; return pwr(2, h - H - 1); } int main(){ ios; int q; cin >> q; while(q--){ cin >> n; if(n == 1){ cout << "0\n"; continue; } lg = 63 - __builtin_clzll(n); for(int h = 0; h <= lg; h ++){ for(int H = 0; H <= h; H ++){ dp[0][h][H] = pd[0][h][H] = check(h, H); if(H < h){ pd[1][h][H] = 2 * check(h + 1, H); dp[1][h][H] = pd[1][h][H] + 1; } else{ pd[1][h][H] = check(h + 1, H) + check(h + 1, H + 1); dp[1][h][H] = pd[1][h][H] + (h > 0); } } } for(int i = 0; i <= 1; i ++){ memset(dp[i][lg + 1], 0, sizeof dp[i][lg + 1]); memset(pd[i][lg + 1], 0, sizeof pd[i][lg + 1]); } for(int l = 2; l <= lg * 2; l ++){ for(int h = 0; h <= lg; h ++){ for(int H = 0; H <= h; H ++){ ll &r1 = pd[l][h][H]; ll &r2 = dp[l][h][H]; if(H < h){ r1 = 2 * pd[l - 1][h + 1][H]; r2 = r1 + dp[l - 1][h - 1][H]; r2 = r2 - pd[l - 2][h][H]; } else{ r2 = r1 = pd[l - 1][h + 1][H + 1] + pd[l - 1][h + 1][H]; if(h){ r2 = r2 + dp[l - 1][h - 1][H - 1]; r2 = r2 - pd[l - 2][h][H]; } } } } memset(dp[l][lg + 1], 0, sizeof dp[l][lg + 1]); memset(pd[l][lg + 1], 0, sizeof pd[l][lg + 1]); } int ans = 0; for(int h = 0; h <= lg; h ++){ for(int H = 0; H <= h; H ++){ int res = 0; ll sum = 0; for(int l = 0; l <= 2 * lg; l ++){ sum += dp[l][h][H]; int res2 = neg(pwr(2, dp[l][h][H] % (mod - 1)), 1); res2 = mul(res2, pwr(2, (n - sum) % (mod - 1))); res = add(res, mul(res2, l)); } ans = add(ans, mul(res, get_cnt(h, H))); } } int inv = pwr(neg(pwr(2, n % (mod - 1)), 1), mod - 2); cout << mul(ans, inv) << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...