QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#137002#241. Chiaki Sequence Revisitedpssxx0 963ms3580kbC++202.6kb2023-08-09 16:34:422023-08-09 16:34:45

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-09 16:34:45]
  • 评测
  • 测评结果:0
  • 用时:963ms
  • 内存:3580kb
  • [2023-08-09 16:34:42]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define db long double

// inline __int128 read()
// {
//     __int128 x = 0, f = 1;
//     char ch = getchar();
//     while (ch < '0' || ch>'9')
//     {
//         if (ch == '-')
//             f = -1;
//         ch = getchar();
//     }
//     while (ch >= '0' && ch <= '9')
//     {
//         x = (x << 1) + (x << 3) + (ch - '0');
//         ch = getchar();
//     }
//     return x * f;
// }
// void print(__int128 x)
// {
//     if (x < 0)
//     {
//         putchar('-');
//         x = -x;
//     }
//     if (x > 9)
//         print(x / 10);
//     putchar(x % 10 + '0');
// }

const double eps = 1e-6;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;

int a[maxn], pow2[100];

int lowbit(int x) {
    return x & (-x);
}

void init() {
    pow2[0] = 1;
    for(int i = 1; i <= 63; i++) {
        pow2[i] = pow2[i - 1] * 2;
    }
}

int n, ans;
int cnt[100];
int pos = 0;

bool check(int x) {
    int now = 1, pre = 0;
    for (int i = pos; i >= 0; i--) {
        cnt[i] = (x / pow2[i] - pre);
        now += (i + 1) * (x / pow2[i] - pre);
        pre += cnt[i];
    }
    if (now >= n) {
        return false;
    } else {
        return true;
    }
}

void solve() {
    // n = read();
    cin >> n;
    int l = 1, r = n;
    pos = 0;
    int now = n;
    while(now != 0) {
        pos++;
        now /= 2;
    }
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    int an = l - 1;
    // cerr << an << '\n';
    int ans = 1;
    int pre = 1;
    for(int i = 0; i <= pos; i++) {
        // cerr << i << '\n';
        int cnt1 = (an + 1) / pow2[i] - (an + 1) / pow2[i + 1];
        // cerr << i << ' ' << cnt1 << ' ' << cnt[i] <<  '\n';
        int beg = pow2[i];
        int end = ((cnt1 - 1) * pow2[i + 1]) + pow2[i];
        ans = (ans + (i + 1) * ((beg + end) * cnt1 / 2) % mod) % mod;
        pre += cnt1 * (i + 1);
    }
    // cout << "?" << ans << '\n';
    ans = (ans + (n - pre) * (an + 1)) % mod;
    // print(ans % mod);
    // putchar('\n');
    cout << ans << '\n';
}

signed main(){
    io;
    init();
    int T = 1;
    // T = read();
    cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 963ms
memory: 3580kb

input:

100000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
1...

output:

1
2
4
6
9
13
17
21
26
32
38
45
53
61
69
77
86
96
106
117
129
141
153
166
180
194
209
225
241
257
273
289
306
324
342
361
381
401
421
442
464
486
509
533
557
581
605
630
656
682
709
737
765
793
822
852
882
913
945
977
1009
1041
1073
1105
1138
1172
1206
1241
1277
1313
1349
1386
1424
1462
1501
1541
158...

result:

wrong answer 10001st lines differ - expected: '550345233', found: '-259202986'