QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#68188#5169. 夹娃娃Chinese_zjc_0 1025ms40060kbC++146.8kb2022-12-15 09:17:172022-12-15 09:17:18

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-15 09:17:18]
  • 评测
  • 测评结果:0
  • 用时:1025ms
  • 内存:40060kb
  • [2022-12-15 09:17:17]
  • 提交

answer

// This Code was made by Chinese_zjc_.
#include <bits/stdc++.h>
// #define debug
template <int MOD>
struct modint
{
    unsigned v;
    modint(unsigned v_ = 0) : v(v_) {}
    modint operator-() const { return v ? MOD - v : *this; }
    modint &operator+=(const modint &X) { return (v += X.v) >= MOD ? v -= MOD : v, *this; }
    modint &operator-=(const modint &X) { return (v += MOD - X.v) >= MOD ? v -= MOD : v, *this; }
    modint &operator*=(const modint &X) { return v = 1llu * v * X.v % MOD, *this; }
    modint &operator/=(const modint &X) { return *this *= X.inv(); }
    modint pow(long long B) const
    {
        B %= MOD - 1;
        if (B < 0)
            B += MOD - 1;
        modint res = 1, A = *this;
        while (B)
        {
            if (B & 1)
                res *= A;
            B >>= 1;
            A *= A;
        }
        return res;
    }
    modint inv() const { return pow(MOD - 2); }
    friend modint operator+(const modint &A, const modint &B) { return modint(A) += B; }
    friend modint operator-(const modint &A, const modint &B) { return modint(A) -= B; }
    friend modint operator*(const modint &A, const modint &B) { return modint(A) *= B; }
    friend modint operator/(const modint &A, const modint &B) { return modint(A) /= B; }
    friend std::istream &operator>>(std::istream &A, modint &B) { return A >> B.v; }
    friend std::ostream &operator<<(std::ostream &A, const modint &B) { return A << B.v; }
    friend bool operator==(const modint &A, const modint &B) { return A.v == B.v; }
    explicit operator bool() const { return v; }
};
const int L = 5;
const int B = 3;
const int M = 2080;
int n, m, MOD;
template <class mint>
struct polynomial
{
    mint v[M];
    unsigned len;
    polynomial() {}
    void fill(const mint &w) { std::fill(v, v + M, w); }
    void assign(mint *X, int size, mint pw[M][M])
    {
        fill(0);
        len = size;
        for (int i = 0; i != M; ++i)
        {
            __uint128_t res = 0;
            for (int j = 0; j != size; ++j)
                res += (unsigned long long)pw[i][j].v * X[j].v;
            v[i] = res % MOD;
        }
    }
    mint &operator[](const int &X) { return v[X]; }
    const mint &operator[](const int &X) const { return v[X]; }
    friend polynomial operator*(const polynomial &A, const polynomial &B)
    {
        polynomial res;
        res.len = A.len + B.len - 1;
        for (int i = 0; i != M; ++i)
            res.v[i] = A[i] * B[i];
        return res;
    }
    friend polynomial operator+(const polynomial &A, const polynomial &B)
    {
        polynomial res;
        res.len = std::max(A.len, B.len);
        for (int i = 0; i != M; ++i)
            res.v[i] = A[i] + B[i];
        return res;
    }
    friend polynomial operator-(const polynomial &A, const polynomial &B)
    {
        polynomial res;
        res.len = std::max(A.len, B.len);
        for (int i = 0; i != M; ++i)
            res.v[i] = A[i] - B[i];
        return res;
    }
};
template <class mint>
void mul(mint *res, mint *A, mint *B)
{
    for (int i = 0; i <= 520; ++i)
        for (int j = 0; j <= i; ++j)
            res[i] += A[j] * B[i - j];
}
template <class mint>
void solve()
{
    using poly = polynomial<mint>;
    mint pw[M][M], a[15][522], tmp[B][1 << L][522], ans[m], val[M][M], p[M + 1];
    poly g[B][1 << L], f[B][1 << L], b[15];
    std::vector<std::tuple<int, int, int>> querys[522];
    for (int i = 0; i != M; ++i)
    {
        pw[i][0] = 1;
        for (int j = 1; j != M; ++j)
            pw[i][j] = pw[i][j - 1] * i;
    }
    p[0] = 1;
    for (int i = 0; i != M; ++i)
        for (int j = i; j >= 0; --j)
            p[j + 1] += p[j], p[j] *= MOD - i;
    for (int i = 0; i != M; ++i)
    {
        mint tmp = 1, lst;
        for (int j = 0; j != M; ++j)
            if (i != j)
                tmp *= i - j + MOD;
        tmp = tmp.inv();
        for (int j = M; j--;)
            val[j][i] = tmp * (lst = p[j + 1] + lst * i);
    }
    for (int i = 0; i != 15; ++i)
        a[i][0] = 1;
    for (int i = 0, cnt, x, y; i != n; ++i)
    {
        std::cin >> cnt;
        while (cnt--)
        {
            std::cin >> x >> y;
            mint v[x];
            for (int j = 520; j > 520 - x * y && j >= 0; --j)
                v[j % x] += a[i][j];
            for (int j = 520; j >= 0; --j)
            {
                if (j - x * y >= 0)
                    v[j % x] += a[i][j - x * y];
                v[j % x] -= a[i][j];
                a[i][j] += v[j % x];
            }
        }
    }
    for (int i = 0; i != B; ++i)
    {
        tmp[i][0][0] = 1;
        for (int j = 0; j != L; ++j)
            std::copy(a[i * L + j], a[i * L + j] + 521, tmp[i][1 << j]);
        for (int j = 1; j != 1 << L; ++j)
            if (j & (j - 1))
                mul(tmp[i][j], tmp[i][j & (j - 1)], tmp[i][j & -j]);
        for (int j = 0; j != 1 << L; ++j)
            g[i][j].assign(tmp[i][j], 521, pw);
    }
    for (int i = 0, x, y, z; i != m; ++i)
    {
        static std::string s;
        std::cin >> s >> y >> z;
        x = 0;
        for (int j = 0; j != n; ++j)
            x = x | (s[j] == '1') << j;
        querys[z - 1].push_back({x, y, i});
    }
    for (int i = 1; i <= 520; ++i)
        for (int j = 0; j != M; ++j)
            val[i][j] += val[i - 1][j];
    for (int i = 0; i != 520; ++i)
    {
        for (int j = 0; j != n; ++j)
            for (int k = 0; k != M; ++k)
                b[j][k] += a[j][i] * pw[k][i];
        for (int j = 0; j != B; ++j)
        {
            f[j][0].fill(1);
            for (int k = 0; k != L; ++k)
                f[j][1 << k] = b[j * L + k];
            for (int k = 1; k != 1 << L; ++k)
                if (k & (k - 1) && __builtin_popcount(k) * i <= 520)
                    f[j][k] = f[j][k & (k - 1)] * f[j][k & -k];
            for (int k = 0; k != 1 << L; ++k)
                f[j][k] = f[j][k] * g[j][(1 << L) - 1 - k];
            for (int k = 0; k != L; ++k)
                for (int l = 0; l != 1 << L; ++l)
                    if (l >> k & 1)
                        f[j][l] = f[j][l] - f[j][l ^ 1 << k];
        }
        for (auto j : querys[i])
        {
            int u = std::get<0>(j), v = std::get<1>(j), w = std::get<2>(j);
            poly res;
            res.fill(1);
            for (int k = 0; k != B; ++k)
                res = res * f[k][u >> (k * L) & ((1 << L) - 1)];
            for (int k = 0; k != M; ++k)
                ans[w] += val[v][k] * res[k];
        }
    }
    for (int i = 0; i != m; ++i)
        std::cout << ans[i] << '\n';
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin >> n >> m >> MOD;
    if (MOD == 998244353)
        solve<modint<998244353>>();
    else
        solve<modint<1000000007>>();
    return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 407ms
memory: 39156kb

input:

1 521 998244353
39 520 520 11 22 414 8 95 18 229 356 26 407 316 10 24 26 19 61 11 130 482 476 420 15 192 193 208 24 19 233 494 217 275 294 26 28 439 20 272 277 28 198 5 335 22 8 28 17 154 78 6 13 175 17 2 5 477 256 200 4 1 36 427 371 439 23 10 65 426 25 24 27 121 29 28 13 12 453
0 520 1
1 519 1
1 51...

output:

38813347
76100715
899989396
959431010
76100720
959431015
899989407
76100733
899989420
76100749
959431051
959431065
76100791
959431106
959431133
959431165
959431203
899989638
959431306
76101080
899989837
959431539
76101354
899990162
76101630
959432096
959432295
899990917
76102506
959433113
76103180
9...

result:

wrong answer 2nd lines differ - expected: '922143638', found: '76100715'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 1025ms
memory: 40060kb

input:

15 52099 998244353
1 9 3
1 9 4
1 9 2
1 8 10
1 4 4
1 3 1
1 2 5
1 4 9
1 1 4
1 9 4
1 7 6
1 1 6
1 2 5
1 5 2
1 3 5
101000000001010 516 1
010001001010101 520 2
000000101000001 519 2
101011111100011 518 1
010110001000111 520 2
000110111100111 516 1
000100101001011 519 3
000111001010011 518 1
00001110010111...

output:

993379058
496689529
131875766
797687294
516999177
516999177
39022588
728354824
552778235
769822588
331666941
99789529
94287883
112750588
756797435
479199177
870912000
361582588
594280447
503496706
400465412
819399177
435456000
504798354
536510471
689332236
727057412
501554824
78733059
85533882
90882...

result:

wrong answer 3rd lines differ - expected: '866368587', found: '131875766'

Subtask #5:

score: 0
Skipped

Dependency #3:

0%

Subtask #6:

score: 0
Skipped

Dependency #4:

0%

Subtask #7:

score: 0
Skipped

Dependency #6:

0%