$A\times B = (\lfloor \frac A M \rfloor \times M + A \mod M) \times (\lfloor \frac B M \rfloor \times M + B \mod M)$

$\lfloor \frac B M \rfloor$为多项式 $a _ 2$，$B \mod M$为多项式 $b _ 2$

$A \times B$
$= (a _ 1 \times M + b _1) \times (a _ 2 \times M + b _ 2)$
$= M ^ 2 \times (a _ 1 \times a _ 2) + M \times (a _ 1 \times b _ 2 + a _ 2 \times b _ 1) + b _ 1 \times b _ 2$

#include <bits/stdc++.h>

#define NS (100005)

using namespace std;

typedef long long LL;

typedef complex<long double> cpx;

const long double PI = acos(-1);
const int M = (1 << 15);

template<typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

int rev[NS << 2];

struct Poly
{
int len, bs; cpx A[NS << 2];
cpx& operator [] (const int a) {return A[a];}
void resize(int a)
{
len = 1, bs = 0;
while (len < a) len <<= 1, bs++;
}
void FFT(int f = 1)
{
for (int i = 0; i < len; i += 1)
{
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bs - 1));
if (i < rev[i]) swap(A[i], A[rev[i]]);
}
for (int l = 1; l < len; l <<= 1)
{
cpx p(cos(PI / l), sin(PI / l) * f);
for (int i = 0; i < len; i += (l << 1))
{
cpx w(1, 0), t1, t2;
for (int j = i; j < i + l; j += 1, w *= p)
{
t1 = A[j], t2 = w * A[j + l];
A[j] = t1 + t2, A[j + l] = t1 - t2;
}
}
}
if (f == -1) for (int i = 0; i < len; i += 1) A[i] /= len;
}
void operator *= (Poly &oth)
{
for (int i = 0; i < len; i += 1) A[i] *= oth[i];
}
} a1, b1, a2, b2, aa, ab, ba, bb;

int n, m, MOD, F1[NS], F2[NS];

void MTT()
{
a1.resize(n + m + 1), b1.resize(n + m + 1);
a2.resize(n + m + 1), b2.resize(n + m + 1);
for (int i = 0; i <= n; i += 1)
a1[i].real(F1[i] / M), b1[i].real(F1[i] % M);
for (int i = 0; i <= m; i += 1)
a2[i].real(F2[i] / M), b2[i].real(F2[i] % M);
a1.FFT(), b1.FFT(), a2.FFT(), b2.FFT();
aa = a1, aa *= a2, ab = a1, ab *= b2, ba = b1, ba *= a2, bb = b1, bb *= b2;
aa.FFT(-1), ab.FFT(-1), ba.FFT(-1), bb.FFT(-1);
}

int main(int argc, char const* argv[])
{
IN(n), IN(m), IN(MOD);
for (int i = 0; i <= n; i += 1) IN(F1[i]);
for (int i = 0; i <= m; i += 1) IN(F2[i]);
MTT();
for (int i = 0; i <= n + m; i += 1)
{
LL a = aa[i].real() + 0.1;
a = a * M % MOD * M % MOD;
a = (a + (LL)(ab[i].real() + 0.5) * M % MOD) % MOD;
a = (a + (LL)(ba[i].real() + 0.5) * M % MOD) % MOD;
a = (a + (LL)(bb[i].real() + 0.5)) % MOD;
printf("%lld ", a);
}
putchar(10);
return 0;
}


#### Remmina

No puzzle that couldn't be solved.