QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#88225#5424. NaN in a HeapzghtyarecrenjWA 3ms3508kbC++142.3kb2023-03-15 17:32:492023-03-15 17:32:51

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-15 17:32:51]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3508kb
  • [2023-03-15 17:32:49]
  • 提交

answer

#include <bits/stdc++.h>

typedef long long ll;
const int mod = 1e9 + 7;

inline int addint(int x) { return x < mod ? x : x - mod; }
inline void Add(int &x, int y) { if ((x += y) >= mod) x -= mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
inline void m3(int &x, int y, int z) { x = (1ll * y * z + x) % mod; }

inline int qpow(int x, int y) {
    int z = 1;
    for (; y; y >>= 1, x = 1ll * x * x % mod)
        if (y & 1) z = 1ll * z * x % mod;
    return z;
}

int pw2[32], f[32][32], g[32], h[32][32], sz[32];

int main() {
    pw2[0] = 1;
    for (int i = 1; i < 32; ++i) pw2[i] = addint(pw2[i - 1] * 2);
    g[1] = 1;
    for (int i = 2; i < 32; ++i) g[i] = mul(pw2[i] - 1 + mod, mul(g[i - 1], g[i - 1]));
    for (int i = 1; i < 32; ++i) {
        for (int j = 1; j < i; ++j) {
            int tmp = mul(g[i], qpow(g[j], mod - 2));
            for (int k = j + i; k <= i; ++k)
                tmp = mul(tmp, mul(pw2[k] - pw2[j] + mod, qpow(addint(pw2[j] - 1 + mod), mod - 2)));
            h[i][j] = tmp;
        }
    }
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        int d = 32 - __builtin_clz(n);
        auto sh = [&](int x) { return d - x + ((n >> (d - x)) & 1); };
        sz[d] = 1;
        for (int i = d - 1; i; --i) sz[i] = addint(sz[i + 1] + pw2[sh(i + 1)]);
        for (int j = 1; j <= d; ++j) f[0][j] = 1;
        for (int i = 1; i <= d; ++i)
            for (int j = 1; j <= d; ++j)
                f[i][j] = mul(f[i - 1][j], sz[i] - pw2[j] + 1 + mod);
        int X = 1;
        for (int i = 1; i <= d; ++i) X = mul(X, sz[i]);
        for (int i = 2; i <= d; ++i) X = mul(X, g[i]);
        int res = 0;
        for (int i = 1; i <= d; ++i) {
            int ers = 1;
            for (int j = 1; j < i; ++j) ers = mul(ers, sz[j]);
            int t0 = mul(X, qpow(ers, mod - 2)), t1 = t0;
            for (int j = 1; j < i; ++j) t1 = mul(t1, sz[j] - sz[i]);
            m3(res, sz[i], qpow(t1, mod - 2));
            int si = sh(i);
            for (int j = 1; j <= si; ++j)
                m3(res, mul(pw2[j] - 1, g[si]),
                    mul(pw2[si - j], qpow(mul(t0, mul(f[i - 1][j], h[si][j])), mod - 2)));
        }
        res = mul(res, qpow(n, mod - 2));
        printf("%d\n", res);
    }
    return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 3508kb

input:

5
1
3
7
10
20221218

output:

1
907407414
525945126
128749399
848948453

result:

wrong answer 2nd numbers differ - expected: '666666672', found: '907407414'