QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#68188 | #5169. 夹娃娃 | Chinese_zjc_ | 0 | 1025ms | 40060kb | C++14 | 6.8kb | 2022-12-15 09:17:17 | 2022-12-15 09:17:18 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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%