QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#848931 | #9945. Circular Convolution | Tobo | WA | 629ms | 84020kb | C++20 | 4.4kb | 2025-01-09 10:52:19 | 2025-01-09 10:52:19 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
// using i64 = long long;
// using i128 = __int128_t;
bool Memory_begin;
#define int long long
#define i64 __int128_t
const int N = 2e5 + 5, P = 4179340454199820289;
// using i64 = long long;
using Poly = vector<int>;
/*---------------------------------------------------------------------------*/
#define MUL(a, b) (i64(a) * (b) % P)
#define ADD(a, b) (((a) += (b)) >= P ? (a) -= P : 0) // (a += b) %= P
#define SUB(a, b) (((a) -= (b)) < 0 ? (a) += P : 0) // ((a -= b) += P) %= P
Poly getInv(int L)
{
Poly inv(L);
inv[1] = 1;
for (int i = 2; i < L; i++)
inv[i] = MUL((P - P / i), inv[P % i]);
return inv;
}
int POW(i64 a, int b = P - 2, i64 x = 1)
{
for (; b; b >>= 1, a = a * a % P)
if (b & 1)
x = x * a % P;
return x;
}
namespace NTT
{
const int g = 3;
Poly Omega(int L)
{
int wn = POW(g, P / L);
Poly w(L);
w[L >> 1] = 1;
for (int i = L / 2 + 1; i < L; i++)
w[i] = MUL(w[i - 1], wn);
for (int i = L / 2 - 1; i >= 1; i--)
w[i] = w[i << 1];
return w;
}
auto W = Omega(1 << 21); // Length
void DIF(int *a, int n)
{
for (int k = n >> 1; k; k >>= 1)
for (int i = 0, y; i < n; i += k << 1)
for (int j = 0; j < k; ++j)
y = a[i + j + k], a[i + j + k] = MUL(a[i + j] - y + P, W[k + j]), ADD(a[i + j], y);
}
void IDIT(int *a, int n)
{
for (int k = 1; k < n; k <<= 1)
for (int i = 0, x, y; i < n; i += k << 1)
for (int j = 0; j < k; ++j)
x = a[i + j], y = MUL(a[i + j + k], W[k + j]),
a[i + j + k] = x - y < 0 ? x - y + P : x - y, ADD(a[i + j], y);
int Inv = P - (P - 1) / n;
for (int i = 0; i < n; i++)
a[i] = MUL(a[i], Inv);
reverse(a + 1, a + n);
}
}
/*---------------------------------------------------------------------------*/
namespace Polynomial
{
// basic operator
int norm(int n) { return 1 << (__lg(n - 1) + 1); }
void norm(Poly &a)
{
if (!a.empty())
a.resize(norm(a.size()), 0);
else
a = {0};
}
void DFT(Poly &a) { NTT::DIF(a.data(), a.size()); }
void IDFT(Poly &a) { NTT::IDIT(a.data(), a.size()); }
Poly &dot(Poly &a, Poly &b)
{
for (int i = 0; i < a.size(); i++)
a[i] = MUL(a[i], b[i]);
return a;
}
// mul / div int
Poly &operator*=(Poly &a, int b)
{
for (auto &x : a)
x = MUL(x, b);
return a;
}
Poly operator*(Poly a, int b) { return a *= b; }
Poly operator*(int a, Poly b) { return b * a; }
Poly &operator/=(Poly &a, int b) { return a *= POW(b); }
Poly operator/(Poly a, int b) { return a /= b; }
// Poly add / sub
Poly &operator+=(Poly &a, Poly b)
{
a.resize(max(a.size(), b.size()));
for (int i = 0; i < b.size(); i++)
ADD(a[i], b[i]);
return a;
}
Poly operator+(Poly a, Poly b) { return a += b; }
Poly &operator-=(Poly &a, Poly b)
{
a.resize(max(a.size(), b.size()));
for (int i = 0; i < b.size(); i++)
SUB(a[i], b[i]);
return a;
}
Poly operator-(Poly a, Poly b) { return a -= b; }
// Poly mul
Poly operator*(Poly a, Poly b)
{
int n = a.size() + b.size() - 1, L = norm(n);
if (a.size() <= 8 || b.size() <= 8)
{
Poly c(n);
for (int i = 0; i < a.size(); i++)
for (int j = 0; j < b.size(); j++)
c[i + j] = (c[i + j] + (i64)a[i] * b[j] % P) % P;
return c;
}
a.resize(L), b.resize(L);
DFT(a), DFT(b), dot(a, b), IDFT(a);
return a.resize(n), a;
}
}
using namespace Polynomial;
bool Memory_end;
signed main()
{
cin.tie(nullptr)->sync_with_stdio(false);
cerr << (&Memory_end - &Memory_begin) / 1048576.0 << "MB" << '\n';
int n;
cin >> n;
Poly a(n), b(n);
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < n; i++)
cin >> b[i];
auto c = a * b;
for (int i = n; i < c.size(); i++)
c[i - n] = (c[i - n] + c[i]) % P;
for (int i = 0; i < n; i++)
cout << c[i] << ' ';
}
/*
*/
詳細信息
Test #1:
score: 100
Accepted
time: 7ms
memory: 19296kb
input:
3 1 1 4 5 1 4
output:
13 22 25
result:
ok 3 number(s): "13 22 25"
Test #2:
score: 0
Accepted
time: 15ms
memory: 19444kb
input:
3 1 2 3 -1 2 0
output:
5 0 1
result:
ok 3 number(s): "5 0 1"
Test #3:
score: 0
Accepted
time: 7ms
memory: 19300kb
input:
3 1 2 4 -1 1 0
output:
3 -1 -2
result:
ok 3 number(s): "3 -1 -2"
Test #4:
score: 0
Accepted
time: 7ms
memory: 19260kb
input:
1 1000000 1000000
output:
1000000000000
result:
ok 1 number(s): "1000000000000"
Test #5:
score: 0
Accepted
time: 446ms
memory: 83992kb
input:
1000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 1000000 numbers
Test #6:
score: 0
Accepted
time: 624ms
memory: 84020kb
input:
1000000 -881218 -558526 -910874 -6842 -969355 -727356 -908202 -230188 -861493 -755231 -547147 -361322 -259909 -134366 -104312 -683109 -972495 -784717 -75027 -899836 -645370 -386525 -440026 -13261 -402678 -624676 -970518 -84749 -454793 -199069 -973352 -771037 -314793 -987539 -422981 -953310 -199002 -...
output:
249834516261376798 250033244986869814 250018516809656471 250043162241643084 250047307005230848 249960143714092741 249955852221357355 250026384381548618 250026566302278862 250107844830331063 250033211167036624 249949178512153648 249898401524703709 249953245638099686 250023894911609754 250055432589110...
result:
ok 1000000 numbers
Test #7:
score: -100
Wrong Answer
time: 629ms
memory: 83804kb
input:
1000000 -244143 -318385 -84411 -659901 -387443 -393190 -721118 -815116 -583259 -194739 -573885 -232923 -61218 -222501 -189798 -554526 -991747 -625587 -612090 -473805 -194134 -941634 -424202 -576051 -909521 -690138 -943368 -891988 -353552 -816696 -885432 -742507 -458420 -600109 -855439 -902837 -80392...
output:
3929265582620977633 3929252340842119730 3929262236348202641 3929290484662069547 3929283851134685588 3929484964507184346 3929128672998664627 3929292646139250904 3929162262444781516 3929340086829035552 3929202486923774863 3929224036807309788 3929263227010124376 3929326992152429467 3929264283699895880 ...
result:
wrong answer 1st numbers differ - expected: '-250074871578842656', found: '3929265582620977633'