QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#481915#8717. 骰子lilabWA 3818ms262896kbC++205.9kb2024-07-17 16:00:312024-07-17 16:00:31

Judging History

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

  • [2024-07-17 16:00:31]
  • 评测
  • 测评结果:WA
  • 用时:3818ms
  • 内存:262896kb
  • [2024-07-17 16:00:31]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long int
#define db double
#define tp ll
#define ptp pair<tp,tp>
#define pdb pair<db,db>
#define umap unordered_map
#define ed '\n'


using namespace std;

tp n, num, sum, flag, ans, tmp, ls, len, wz, pos, m, k, p, q;
tp sqrtn;
tp lt, rt, mid;
tp min1, min2, min3, max1, max2, max3;
string s;
tp h, w, t;

namespace anymod_poly {
    tp mod;

    tp ksm(tp a, tp b, tp p) {
        tp lsans = 1;
        while (b) {
            if (b & 1ll) {
                lsans = (lsans * a) % p;
            }
            a = (a * a) % p;
            b >>= 1;
        }
        return lsans;
    }

    tp inv(tp x, tp mod) { return ksm(x, mod - 2, mod); }

    const tp mod1 = 998244353, mod2 = 1004535809, mod3 = 469762049, G = 3;
    const ll mod_1_2 = static_cast<ll> (mod1) * mod2;
    const tp inv_1 = inv(mod1, mod2), inv_2 = inv(mod_1_2 % mod3, mod3);
    struct Int {
        ll A, B, C;
        explicit Int() { }
        explicit Int(ll __num) : A(__num), B(__num), C(__num) { }
        explicit Int(ll __A, ll __B, ll __C) : A(__A), B(__B), C(__C) { }
        static Int reduce(const Int& x) {
            return Int(x.A + (x.A >> 31 & mod1), x.B + (x.B >> 31 & mod2), x.C + (x.C >> 31 & mod3));
        }
        friend Int operator + (const Int& lhs, const Int& rhs) {
            return reduce(Int(lhs.A + rhs.A - mod1, lhs.B + rhs.B - mod2, lhs.C + rhs.C - mod3));
        }
        friend Int operator - (const Int& lhs, const Int& rhs) {
            return reduce(Int(lhs.A - rhs.A, lhs.B - rhs.B, lhs.C - rhs.C));
        }
        friend Int operator * (const Int& lhs, const Int& rhs) {
            return Int(static_cast<ll> (lhs.A) * rhs.A % mod1, static_cast<ll> (lhs.B) * rhs.B % mod2, static_cast<ll> (lhs.C) * rhs.C % mod3);
        }
        tp get() {
            ll x = static_cast<ll> (B - A + mod2) % mod2 * inv_1 % mod2 * mod1 + A;
            return (static_cast<ll> (C - x % mod3 + mod3) % mod3 * inv_2 % mod3 * (mod_1_2 % mod) % mod + x) % mod;
        }
    };

    tp lim, s;
    vector<tp>rev;
    vector<Int>Wn;
    void poly_init(tp n) {
        s = -1, lim = 1;
        while (lim < n) lim <<= 1, ++s;
        rev = vector<tp>(lim + 5);
        Wn = vector<Int>(lim + 5);
        for (register tp i = 1; i < lim; ++i) rev[i] = rev[i >> 1] >> 1 | (i & 1) << s;
        const Int t(ksm(G, (mod1 - 1) / lim, mod1), ksm(G, (mod2 - 1) / lim, mod2), ksm(G, (mod3 - 1) / lim, mod3));
        Wn[0] = Int(1);
        for (auto it = Wn.begin(); it != Wn.begin() + lim; ++it) *(it + 1) = *it * t;
    }
    void ntt(Int* A, const tp op) {//传入的数组尺寸至少要比lim大
        for (register tp i = 1; i < lim; ++i) if (i < rev[i]) std::swap(A[i], A[rev[i]]);
        for (register tp mid = 1; mid < lim; mid <<= 1) {
            const tp t = lim / mid >> 1;
            for (register tp i = 0; i < lim; i += mid << 1) {
                for (register tp j = 0; j < mid; ++j) {
                    const Int W = op ? Wn[t * j] : Wn[lim - t * j];
                    const Int X = A[i + j], Y = A[i + j + mid] * W;
                    A[i + j] = X + Y, A[i + j + mid] = X - Y;
                }
            }
        }
        if (!op) {
            const Int ilim(inv(lim, mod1), inv(lim, mod2), inv(lim, mod3));
            for (register Int* i = A; i != A + lim; ++i) *i = (*i) * ilim;
        }
    }

    void mul(Int* a, Int* b, Int* c) {
        for (tp i = 0; i < lim; ++i) c[i] = a[i] * b[i];
        ntt(c, 0);
        for (tp i = m + 1; i < lim; i++) {//去除大于m的阶
            c[i] = Int(0);
        }
        ntt(c, 1);
    }

}

using namespace anymod_poly;

Int b[520], bb[520];
Int a[1505][520];
tp qj[1505][1505];
Int tj[15][1505][520];

void qj_init(tp k,tp lr,tp rr) {
    if (lr == rr) {
        qj[lr][rr] = k;
        mul(a[lr], bb, tj[k][lr]);
        ntt(tj[k][lr], 0);
        return;
    }
    tp mid = (lr + rr) >> 1;

    mul(a[mid], bb, tj[k][mid]);
    for (tp i = mid - 1; i >= lr; i--) {
        mul(tj[k][i + 1], a[i], tj[k][i]);
    }

    for (tp i = 0; i < lim; i++) {
        tj[k][mid + 1][i] = a[mid + 1][i];
    }
    for (tp i = mid + 2; i <= rr; i++) {
        mul(tj[k][i - 1], a[i], tj[k][i]);
    }

    for (tp i = lr; i <= rr; i++) {
        ntt(tj[k][i], 0);
    }

    for (tp i = lr; i <= mid; i++) {
        for (tp j = mid + 1; j <= rr; j++) {
            qj[i][j] = k;
        }
    }

    qj_init(k + 1, lr, mid);
    qj_init(k + 1, mid + 1, rr);
}


void init() {

}

void clear() {

}

void solve() {
    mod = 1e9 + 7;
    cin >> n >> m >> q;
    sqrtn = sqrt(n);
    poly_init(2 * m + 1);

    for (tp i = 0; i <= m; i++) {
        cin >> ls;
        b[i] = Int(ls % mod);
        bb[m - i] = b[i];
    }
    //将bb转化
    ntt(bb, 1);
    for (tp i = 1; i <= n; i++) {
        for (tp j = 0; j <= m; j++) {
            cin >> ls;
            a[i][j] = Int(ls % mod);
        }
    }

    //将a[i]转化
    for (tp i = 1; i <= n; i++) {
        ntt(a[i], 1);
    }

    qj_init(1,1,n);



    for (tp i = 1; i <= q; i++) {
        cin >> lt >> rt;
        k = qj[lt][rt];
        ans = 0;
        if (lt == rt) {
            ans = tj[k][lt][m].get();
        }
        else {
            for (tp j = 0; j <= m; j++) {
                ans = (ans + (tj[k][lt][j].get() * tj[k][rt][m - j].get()) % mod) % mod;
            }
        }
        cout << ans << ed;
    }




}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int _t = 1;
    //cin >> _t;
    init();
    while (_t--) {
        solve();
    }
}
//样例
/*

3 3 3
4 3 2 1
0 1 0 1000000007
0 500000004 0 500000004
0 0 500000004 500000004
1 1
1 2
1 3


3 3 6
4 3 2 1
1000000007 0 1 0
1000000007 1 0 0
1000000007 0 1 0
1 1
1 2
1 3
2 2
2 3
3 3


*/


详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 13924kb

input:

3 3 3
4 3 2 1
0 1 0 1000000007
0 500000004 0 500000004
0 0 500000004 500000004
1 1
1 2
1 3

output:

3
1
0

result:

ok 3 number(s): "3 1 0"

Test #2:

score: 0
Accepted
time: 0ms
memory: 13924kb

input:

3 3 6
4 3 2 1
1000000007 0 1 0
1000000007 1 0 0
1000000007 0 1 0
1 1
1 2
1 3
2 2
2 3
3 3

output:

2
1
0
3
1
2

result:

ok 6 numbers

Test #3:

score: 0
Accepted
time: 1ms
memory: 9820kb

input:

1 1 1
604063100 57375033
742299910 257700098
1 1

output:

148903503

result:

ok 1 number(s): "148903503"

Test #4:

score: -100
Wrong Answer
time: 3818ms
memory: 262896kb

input:

1500 200 600000
253665324 876103781 804024983 929290295 908790466 176299158 528078340 696679927 416465140 509641654 705083449 361711737 250659645 735832780 35321360 383752049 203979021 178832532 785212637 514502839 169840231 65809146 504755349 516829442 382478309 901925498 142312128 782336477 741339...

output:

14916657
6295139
284229519
942884105
145789457
411415569
878173365
102454969
855759202
742220967
214714000
861825849
632396960
781854019
372367698
976635231
245123744
229698809
781418151
799422355
295185377
497454234
268344522
72616156
632858175
908637269
41123229
284213794
189298527
184889077
29509...

result:

wrong answer 1st numbers differ - expected: '66394849', found: '14916657'