QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#130854 | #618. 多项式乘法 | GoatGirl98# | 0 | 6ms | 17140kb | C++17 | 6.9kb | 2023-07-25 14:11:10 | 2023-07-25 14:11:11 |
Judging History
answer
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <assert.h>
typedef long long ll;
typedef __int128_t lll;
namespace FastIO
{
char buf[1 << 21], *p1 = buf, *p2 = buf;
inline char nc() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++; }
int rd()
{
int ret = 0;
char ch = nc();
while (ch < '0' || ch > '9')
ch = nc();
while (ch >= '0' && ch <= '9')
{
ret = (ret << 1) + (ret << 3) + (ch ^ 48);
ch = nc();
}
return ret;
}
char Buf[1 << 21], out[20];
int P, out_size;
void flush() { fwrite(Buf, 1, out_size, stdout), out_size = 0; }
void _putc(char ch) { Buf[out_size++] = ch; }
void wt(ll x, char ch = ' ')
{
if (out_size >= 1 << 20)
flush();
if (x < 0)
Buf[out_size++] = 45, x = -x;
do
out[++P] = (x % 10) ^ 48;
while (x /= 10);
do
Buf[out_size++] = out[P];
while (--P);
Buf[out_size++] = ch;
}
struct IOFlush
{
~IOFlush() { flush(); }
} tail;
}
using namespace FastIO;
// NTT Solver : use for multiple case : n | (p - 1)
// primitive root : 3
// 998244353 (2^23 * 7 * 17 + 1)
// 1004535809 (2^21 * 479 + 1)
// 1007681537 (2^20 * 31^2 + 1)
// 1051721729 (2^20 * 17 * 59 + 1)
namespace Arbitrary_NTT_Solver
{
// int arbitrary_mod;
inline int add(int a, int b, int p) { return (a + b >= p) ? (a + b - p) : (a + b); }
inline int sub(int a, int b, int p) { return (a < b) ? (a - b + p) : (a - b); }
inline int qpow(int a, int b, int p)
{
int ret = 1;
while (b)
{
if (b & 1)
ret = (1ll * ret * a) % p;
b >>= 1;
a = (1ll * a * a) % p;
}
return ret;
}
const int N = (1 << 18) | 3;
// modulo 3
const int M[3] = {1004535809, 1007681537, 1045430273}, proot = 3;
const lll all_mod = (lll)1004535809 * (lll)1007681537 * (lll)1045430273;
const lll MP[3] = {all_mod + (lll)1053460784322969601ll * (lll)(-480795620), all_mod + (lll)1050172145041145857ll * (lll)(-401215089), all_mod + (lll)1012252187984658433ll * (lll)(-128816555)};
struct MOD3
{
int reminder[3];
// assume val is lesser than mod
void init(int val) { reminder[0] = reminder[1] = reminder[2] = val; }
MOD3 inv() const
{
MOD3 ret;
for (int i = 0; i < 3; ++i)
ret.reminder[i] = qpow(reminder[i], M[i] - 2, M[i]);
return ret;
}
MOD3 operator+ (const MOD3& o) const
{
MOD3 ret;
for (int i = 0; i < 3; ++i)
ret.reminder[i] = add(reminder[i], o.reminder[i], M[i]);
return ret;
}
MOD3 operator- (const MOD3& o) const
{
MOD3 ret;
for (int i = 0; i < 3; ++i)
ret.reminder[i] = sub(reminder[i], o.reminder[i], M[i]);
return ret;
}
MOD3 operator* (const MOD3& o) const
{
MOD3 ret;
for (int i = 0; i < 3; ++i)
ret.reminder[i] = (1ll * reminder[i] * o.reminder[i]) % M[i];
return ret;
}
lll val() const
{
lll ret = 0;
for (int i = 0; i < 3; ++i)
ret = (ret + MP[i] * reminder[i]) % all_mod;
return ret;
}
};
bool initialized;
int L, brev[N]; // Butterfly operation
MOD3 w[N], v[N], mod_a[N], mod_b[N];
void init(int _L)
{
L = _L;
initialized = 1;
for (int i = 0; i < 3; ++i)
assert(!((M[i] - 1) & ((1 << L) - 1)));
for (int i = 0; i < (1 << L); ++i)
brev[i] = (brev[i >> 1] >> 1) | ((i & 1) << (L - 1));
w[0].init(1), v[0].init(1);
for (int i = 0; i < 3; ++i)
w[1].reminder[i] = qpow(proot, (M[i] - 1) >> L, M[i]);
v[1] = w[1].inv();
for (int i = 2; i < (1 << L); ++i)
w[i] = w[i - 1] * w[1], v[i] = v[i - 1] * v[1];
}
struct initializer
{
// length is adjustable
initializer() { init(18); }
}arbitrary_ntt_init;
void arbitrary_ntt(MOD3 a[], int lgn, int flag)
{
int n = 1 << lgn;
for (int i = 0; i < n; ++i)
{
int rv = brev[i] >> (L - lgn);
if (rv < i)
{
MOD3 tmp = a[rv];
a[rv] = a[i], a[i] = tmp;
}
}
int fa = L;
MOD3 *q = (flag == 1) ? w : v;
for (int t = 1; t < n; t <<= 1)
{
--fa;
for (int i = 0; i < n; i += (t << 1))
{
MOD3 *p = a + i;
for (int j = 0; j < t; ++j)
{
MOD3 x = p[j + t] * q[j << fa];
p[j + t] = p[j] - x, p[j] = p[j] + x;
}
}
}
if (flag == -1)
{
MOD3 inv_n;
inv_n.init(n), inv_n = inv_n.inv();
for (int i = 0; i < n; ++i)
a[i] = a[i] * inv_n;
}
}
void mul(int a[], int n, int b[], int m, lll res[])
{
// multiple case
memset(res, 0, sizeof(res[0]) * (n + m + 1));
// brute force
if (n < 100 / (m + 1) || n < 3 || m < 3)
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= m; ++j)
res[i + j] = res[i + j] + a[i] * b[j];
// FFT
else
{
assert(initialized);
int lgk = 0, k = 1, len = n + m;
while ((1 << lgk) <= len)
++lgk, k <<= 1;
for (int i = 0; i <= n; ++i)
mod_a[i].init(a[i]);
for (int i = 0; i <= m; ++i)
mod_b[i].init(b[i]);
// multiple_case
memset(mod_a + (n + 1), 0, sizeof(MOD3) * (k - n - 1));
memset(mod_b + (m + 1), 0, sizeof(MOD3) * (k - m - 1));
arbitrary_ntt(mod_a, lgk, 1), arbitrary_ntt(mod_b, lgk, 1);
for (int i = 0; i < k; ++i)
mod_a[i] = mod_a[i] * mod_b[i];
arbitrary_ntt(mod_a, lgk, -1);
for (int i = 0; i <= n + m; ++i)
res[i] = mod_a[i].val();
}
}
}
const int maxn = 10010;
int a[maxn + 10], b[maxn + 10];
lll c[(maxn << 1) + 10];
int main()
{
int T = 1;
while (T--)
{
int n = rd(), m = n;
for (int i = 0; i <= n; ++i)
a[i] = rd();
for (int i = 0; i <= m; ++i)
b[i] = rd();
Arbitrary_NTT_Solver::mul(a, n, b, m, c);
for (int i = 0; i <= n + m; ++i)
wt(c[i]);
_putc('\n');
}
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 6ms
memory: 17140kb
input:
96 96 600395131 184265451 942971382 534262851 830366882 542271170 294355449 501371170 797809599 964826049 276651245 375755165 662619442 941920605 328216963 507795473 460271147 874920847 818231910 156789488 590591583 732194508 793983630 93566697 836155866 305319153 432040686 621119061 835023373 57138...
output:
46494256032 290780515036126917 382559894203486516 1078861303473279363 1407135882044665022 2146489333579990554 2123336467885905860 2940115890398863505 2494490874947040312 3120354050006560125 3423441073759901686 3520676269647523339 4353893295590122954 3764532260048258382 4348386858030270562 4381674288...
result:
wrong answer 1st numbers differ - expected: '683858396', found: '46494256032'
Test #2:
score: 0
Wrong Answer
time: 4ms
memory: 15564kb
input:
4992 4994 471194390 313639917 705341086 119536186 430124603 244978845 185588341 13731324 707132801 88167972 927324568 846658454 523684029 5133605 767200778 502476309 539772401 778154025 266136872 183516351 260704325 49303370 475056182 928574546 740424153 277920667 708439854 746983628 839491869 53579...
output:
4424707801404 417481900478456756 412364330351424508 1167605840797035342 1010295631898376551 1690861672538444806 1567072869332352766 1715368813093105846 1760421884470523468 2410965333215206051 1774205862949461642 2868850442814801260 2693894078996671983 3183191790395101014 3196911526603420519 40648268...
result:
wrong answer 1st numbers differ - expected: '700935456', found: '4424707801404'
Test #3:
score: 0
Time Limit Exceeded
input:
29995 29992 417238081 53580806 733071257 224121793 786137422 127072245 129083351 988357079 246853229 150935424 596994106 975796660 838029970 619117898 328485797 948485083 574261409 79312345 596346086 489787404 929520168 515647000 211731260 50868568 811515357 428215135 498099163 644485329 802849075 3...
output:
result:
Test #4:
score: 0
Time Limit Exceeded
input:
100000 99993 812398607 947396010 797321381 883949986 56052416 586258761 193247973 611124334 773505112 142179482 565466227 140875825 79890768 893500101 553768089 648879319 480419657 915530184 799329430 494818755 793895824 851865180 459534006 259473419 610037701 472768430 868914058 887444584 588850309...
output:
result:
Test #5:
score: 0
Runtime Error
input:
999993 999994 388529697 811245378 165909114 295553883 667981275 78502012 400874009 139394758 249494489 4636487 997712665 259780805 431039016 716944209 709300152 356513646 823185021 699568300 650937921 859190797 899514799 785648601 933470757 627225124 349752104 471458923 456404256 48134357 315599086 ...