MTT
<pre><code class="language-cpp">#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 262144;
namespace MTT{
const double PI = acos(-1);
struct comp{
double x, y;
comp(): x(0), y(0) { }
comp(const double &_x, const double &_y): x(_x), y(_y) { }
};
inline comp operator+(const comp &a, const comp &b) { return comp(a.x + b.x, a.y + b.y); }
inline comp operator-(const comp &a, const comp &b) { return comp(a.x - b.x, a.y - b.y); }
inline comp operator*(const comp &a, const comp &b) { return comp(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x); }
inline comp conj(const comp &a) { return comp(a.x, -a.y); }
comp w[maxn + 5];
int bitrev[maxn + 5];
int mod;
void fft(comp *a, const int &n){
for(int i = 0; i < n; i++) if (i < bitrev[i]) swap(a[i], a[bitrev[i]]);
for (int i = 2, lyc = n >> 1; i <= n; i <<= 1, lyc >>= 1){
for (int j = 0; j < n; j += i){
comp *l = a + j, *r = a + j + (i >> 1), *p = w;
for(int k = 0; k < (i >> 1); k++){
comp tmp = *r * *p;
*r = *l - tmp, *l = *l + tmp;
++l, ++r, p += lyc;
}
}
}
}
inline void fft_prepare(int n)
{
int bits = 0;
while((1 << bits) < n) bits++;
for(int i = 0; i < n; i++) bitrev[i] = bitrev[i >> 1] >> 1 | ((i & 1) << (bits - 1));
for(int i = 0; i < n; i++) w[i] = comp(cos(2 * PI * i / n), sin(2 * PI * i / n));
}
inline void conv(int *x, int *y, int *z, int n)
{
for(int i = 0; i < n; i++) (x[i] += mod) %= mod, (y[i] += mod) %= mod;
static comp a[maxn + 5], b[maxn + 5];
static comp dfta[maxn + 5], dftb[maxn + 5], dftc[maxn + 5], dftd[maxn + 5];
for(int i = 0; i < n; i++) a[i] = comp(x[i] & 32767, x[i] >> 15);
for(int i = 0; i < n; i++) b[i] = comp(y[i] & 32767, y[i] >> 15);
fft(a, n), fft(b, n);
for(int i = 0; i < n; i++){
int j = (n - i) & (n - 1);
static comp da, db, dc, dd;
da = (a[i] + conj(a[j])) * comp(0.5, 0);
db = (a[i] - conj(a[j])) * comp(0, -0.5);
dc = (b[i] + conj(b[j])) * comp(0.5, 0);
dd = (b[i] - conj(b[j])) * comp(0, -0.5);
dfta[j] = da * dc;
dftb[j] = da * dd;
dftc[j] = db * dc;
dftd[j] = db * dd;
}
for(int i = 0; i < n; i++) a[i] = dfta[i] + dftb[i] * comp(0, 1);
for(int i = 0; i < n; i++) b[i] = dftc[i] + dftd[i] * comp(0, 1);
fft(a, n), fft(b, n);
for(int i = 0; i < n; i++){
int da = (ll)(a[i].x / n + 0.5) % mod;
int db = (ll)(a[i].y / n + 0.5) % mod;
int dc = (ll)(b[i].x / n + 0.5) % mod;
int dd = (ll)(b[i].y / n + 0.5) % mod;
z[i] = (da + ((ll)(db + dc) << 15) + ((ll)dd << 30)) % mod;
}
}
}
int main(){
int n, m;
static int a[maxn + 5], b[maxn + 5], c[maxn + 5];
scanf("%d%d%d", &n, &m, &MTT::mod); //n,m分别表示多项式最高次数
for(int i = 0; i <= n; i++) scanf("%d", a + i);
for(int i = 0; i <= m; i++) scanf("%d", b + i);
int tn = 1;
while(tn < n + m + 1) tn <<= 1;
MTT::fft_prepare(tn);
MTT::conv(a, b, c, tn);
for(int i = 0; i <= n + m; i++) (c[i] += MTT::mod) %= MTT::mod, printf("%d ", c[i]);
printf("\n");
return 0;
}</code></pre>