| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 623403 |
2022-08-05T14:25:59 Z |
Arinoor |
Party (INOI20_party) |
C++17 |
|
239 ms |
3216 KB |
#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 = 60;
const int mod = 1e9 + 7;
const int inf = 1e9 + 10;
ll n;
int dp[maxn << 1][maxn][maxn], pd[maxn << 1][maxn][maxn], pw[maxn], lg;
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 pw[max(0, h - H - 1)];
if(!check(h, H))
return 0;
return pw[h - H - 1];
}
int main(){
ios;
pw[0] = 1;
for(int i = 1; i < maxn; i ++)
pw[i] = add(pw[i - 1], pw[i - 1]);
int q; cin >> q;
while(q--){
cin >> n;
if(n == 1){
cout << "0\n";
continue;
}
lg = 63 - __builtin_clzll(n);
int inv = pwr(2, mod - 2);
for(int h = 0; h <= lg; h ++){
for(int H = 0; H <= h; H ++){
dp[0][h][H] = pd[0][h][H] = dp[1][h][H] = pd[1][h][H] = 1;
if(check(h, H)){
dp[0][h][H] = 2;
pd[0][h][H] = inv;
int cnt = 0;
if(H < h){
cnt = 2 * check(h + 1, H) + 1;
}
else{
cnt = check(h + 1, H) + check(h + 1, H + 1) + (h > 0);
}
dp[1][h][H] = pwr(2, cnt);
pd[1][h][H] = pwr(inv, cnt);
}
}
}
for(int l = 2; l <= lg * 2; l ++){
for(int h = max(0, l - lg); h <= lg; h ++){
for(int H = 0; H <= h; H ++){
int &r1 = dp[l][h][H];
int &r2 = pd[l][h][H];
r1 = r2 = 1;
if(!check(h, H))
continue;
int cnt;
if(H < h){
if(h < lg){
r1 = mul(dp[l - 1][h + 1][H], dp[l - 1][h + 1][H]);
r2 = mul(pd[l - 1][h + 1][H], pd[l - 1][h + 1][H]);
}
r1 = mul(r1, dp[l - 1][h - 1][H]);
r2 = mul(r2, pd[l - 1][h - 1][H]);
cnt = 2 * check(h + 1, H) + 1;
}
else{
if(h < lg){
r1 = mul(dp[l - 1][h + 1][H], dp[l - 1][h + 1][H + 1]);
r2 = mul(pd[l - 1][h + 1][H], pd[l - 1][h + 1][H + 1]);
}
if(h){
r1 = mul(r1, dp[l - 1][h - 1][H - 1]);
r2 = mul(r2, pd[l - 1][h - 1][H - 1]);
}
cnt = check(h + 1, H + 1) + check(h + 1, H) + (h > 0);
}
if(l > 2)
cnt --;
if(cnt == 2){
r1 = mul(r1, mul(pd[l - 2][h][H], pd[l - 2][h][H]));
r2 = mul(r2, mul(dp[l - 2][h][H], dp[l - 2][h][H]));
}
else if(cnt == 1){
r1 = mul(r1, pd[l - 2][h][H]);
r2 = mul(r2, dp[l - 2][h][H]);
}
else if(cnt == 3){
r1 = mul(r1, pwr(pd[l - 2][h][H], 3));
r2 = mul(r2, pwr(dp[l - 2][h][H], 3));
}
}
}
}
int ans = 0;
int tot = pwr(2, n % (mod - 1));
for(int h = 0; h <= lg; h ++){
for(int H = 0; H <= h; H ++){
int res = 0;
int p = tot;
for(int l = 0; l <= 2 * lg; l ++){
p = mul(p, pd[l][h][H]);
int cnt = mul(neg(dp[l][h][H], 1), p);
res = add(res, mul(cnt, l));
}
ans = add(ans, mul(res, get_cnt(h, H)));
}
}
inv = pwr(neg(tot, 1), mod - 2);
cout << mul(ans, inv) << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
239 ms |
3188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
237 ms |
3216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
