QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#481915 | #8717. 骰子 | lilab | WA | 3818ms | 262896kb | C++20 | 5.9kb | 2024-07-17 16:00:31 | 2024-07-17 16:00:31 |
Judging History
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'