小学生都能看懂的转置原理、多项式复合（逆）2log 做法！

cancan123456 · 2024-03-25 21:29:33 · 题解

noshi91 好闪，拜谢 noshi91。

Bostan-Mori 在二元分式的拓展

考虑如下问题：给定 n 次多项式 F(x)，如何快速计算 [x^n]F^i(x),0\le i\le n，不妨设 [x^0]F(x)=0。

如果 [x^0]F(x)\ne0，我们设 c=[x^0]F(x)，那么 [x^k]F^n(x)=\sum_{j=0}^i\binom ijc^j[x^k](F(x)-c)^{i-j}，可以利用卷积从 F(x)-c 的答案中求出（笑点解析：我思考了一分钟才意识到可以拆组合数卷）。

由众所周知的展开式：\dfrac1{1-F}=\sum_{i\ge0}F^i，这等价于计算分式 [x^n]\dfrac1{1-yF(x)}。

考虑 Bostan-Mori 算法，设现在的问题是求解 [x^n]\dfrac{U(x,y)}{V(x,y)}，上下两边同乘 V(-x,y)，则分母 V(x,y)V(-x,y) 只含有 x 的偶数次幂乘 y 的任意次幂，根据 n 的奇偶性可以保留分子的奇次项或偶次项，中间 x 的次数超过 n 的项可以直接扔掉。

边界情况是 n=0 时直接返回 \dfrac{[x^0]U(x)}{[x^0]V(x)}，不需要带余除法，直接乘 [x^0]V(x) 的乘法逆。

注意到每次迭代二元多项式的项数都是 O(n) 项，所以之间复杂度是正确的 O(n\log^2n)。

如果你不知道怎么做二维多项式乘法，很简单，我们把 x^iy^j 这一项的系数映射到 x^{i(n+m+1)+j}，其中 n,m 是两个多项式 y 的最高幂，然后直接进行普通多项式相乘，再把系数转回二维多项式就做完了。

拉格朗日反演

本节证明来自 https://www.cnblogs.com/gsjz/p/16187813.html。

注意到多项式复合的单位元是 x，仿照乘法逆的定义，我们定义多项式复合逆：若 G(F(x))=x，则称 F,G 互为（多项式）复合逆，记作 G(x)=F^{\langle-1\rangle}(x)。

这一段中，我们只考虑 [x^0]F(x)=0 的多项式，[x^1]F(x)\ne0，因为这样的多项式的 k 次幂的第 k 项一定不是 0，且更低项一定是 0。

我们将多项式扩展到含有负次幂的形式洛朗级数，类似多项式，形式洛朗级数的定义为：

并且存在一个 n_0 满足对于任意 i<n_0，有 a_i=0，且 a_{n_0}\ne0（如果所有的 a_i 都是 0 我们也认为这是一个形式洛朗级数）。

形式洛朗级数的乘法类似多项式定义即可，对两个 n_0 分别是 n_F,n_G 的形式洛朗级数 F,G，定义：

后面的除法是两个 n_0 等于 0 的洛朗级数，即存在乘法逆的多项式，因此这个定义是良好的，现在我们可以定义形式洛朗级数的整数幂了。

定义一个形式洛朗级数 F(x) 的形式留数为：[x^{-1}]F(x)。

则显然，一个形式洛朗级数的导数的形式留数为 0。

定理：对于 n_0=1 的形式洛朗级数 F(x)，有 [x^{-1}]F'(x)F^k(x)=[k=-1]。

证明：分讨，若 k\ne-1，容易验证 F'(x)F^k(x)=\left(\dfrac1{k+1}F^{k+1}(x)\right)'。

显然其值为 0。

否则有（下式中 F_i=[x_i]F(x)，右侧分子分母同除 F_1）：

我们知道这个分式是一个 n_0=0 且常数项为 1 的形式洛朗级数乘 x^{-1}，那么其形式留数一定为 1。

定理（拉格朗日反演）：对于 n_0=1 的形式洛朗级数 F(x)，有：

证明：根据复合逆的定义有 F(F^{\langle-1\rangle}(x))=x，同时取 k 次幂有 F^k(F^{\langle-1\rangle}(x))=x^k，同时求导可得 (F^k)'\Big(F^{\langle-1\rangle}(x)\Big)F^{\langle-1\rangle}(x)'=kx^{k-1}，同乘 (F^{\langle-1\rangle}(x))^{-n} 可得：

我承认这东西看起来混乱不堪，但是你推一遍就能发现这确实是对的，我们继续：

对两边取形式留数：

奇迹发生了，我们有：F^{\langle-1\rangle}(x)^{i-1-n}F^{\langle-1\rangle}(x)'=[i=n]，因此：

根据拉格朗日反演容易验证扩展拉格朗日反演：

你可能会疑惑，这和我看到的这个：

不太一样？其实很简单，右边的括号里面提出一个 x^n，然后就变成了拉格朗日反演的式子。

现在我们可以考虑多项式复合幂了，我们设 [x^0]F(x)=0 且 v=[x^1]F(x)，令 G(x)=\dfrac xv 带入扩展拉格朗日变换并进行一些简单的推导，可以得到：

其中 H(x)=\dfrac{F(x)}v，注意到括号里的式子的常数项是 1，因此可以直接取 \ln 乘 -\dfrac1n 再取 \exp 得到复合逆。

转置原理

转置原理是说：如果存在一个算法 A 输入 n 个数 a_i 输出 m 个数 b_j，并且可以写成如下形式：

其中 M 是一个 m\times n 的矩阵。

那么存在一个算法，输入 m 个数 b_j 输出 n 个数 a_i，可以写成如下形式：

其中 M^T 为 M 的转置。

如何进行转化？转置原理基于如下定理：

这就意味着我们需要从后向前考虑算法的每个步骤，依次找到其转置，替换即可。

解决多项式复合

我们考虑将求 G(F(x)) 的过程写为一个矩阵形式。

不妨设 G(x) 的系数为输入的 a_k，复合结果的系数为输出的 b_j，那么有：

其对应的矩阵 M 满足 M_{j,k}=[x^j]F^k(x)，则其转置问题为给定 b_j 求出：

考虑构造 P(x) 满足 [x^n]\dfrac{P(x)}{1-yF(x)}=\sum_{k\ge0}a_ky^k，将其转换为求二元分式，这样就可以用 Bostan-Mori 算法了。展开一下：

要让对应项相等，这要求：

展开左侧的卷积：

因此 P(x) 只需要满足 [x^{n-j}]P(x)=b_j 即可，这意味着 P(x)=\sum_{j=0}^nb_{n-j}x^j。

这样问题就解决了……吗？

没有，这只是转置问题的解，我们还需要求 Bostan-Mori 的转置算法。

最终冲刺！Bostan-Mori 的转置算法

需要注意的是，Bostan-Mori 看起来有三个输入 n,U(x,y),V(x,y) 一个输出，但是由于 V(x,y) 可以由 F(x) 得到，n 也是给定的所以真正的输入只有 U(x,y) 一个，所以可以将 V(x,y),n 看作 Bostan-Mori 的参数。

方便起见，我们设 \text{BM}_{n,V(x,y)} 为以 n,V(x,y) 为参数调用 Bostan-Mori 算法时对 U(x,y) 的变换矩阵。

先考虑多项式乘法的转置，给定一个 n 次（保证 n 是 2 的幂）多项式 G(x)，多项式乘法就是，输入 F(x)，求出 H(x)=F(x)\ast G(x)，方便起见，\ast 是循环卷积。

这个算法可以用 FFT/NTT 快速实现，可以表示为：

容易发现这三个矩阵的转置都是其自身，多项式乘法的转置就是：

注意这里 \text{FFT}_n 和 \text{IFFT}_n 的顺序是相反的，我们就找到了多项式乘法的转置。

现在考虑 Bostan-Mori 的转置。

然后就真的结束了，时间复杂度为 O(n\log^2n)。

#include <cstdio>
#include <vector>
#include <algorithm>
using std::scanf;
using std::printf;
using std::vector;
using std::reverse;
using std::max;
typedef long long ll;
const ll mod = 998244353, g = 3;
const ll invg = 332748118, sqrt_1 = 911660635;
const ll inv2 = 499122177, inv_sqrt_1 = 86583718;
ll pow(ll a, ll b) {
    ll ans = 1;
    while (b != 0) {
        if ((b & 1) == 1) {
            ans = ans * a % mod;
        }
        a = a * a % mod;
        b = b / 2;
    }
    return ans;
}
ll inv(ll x) {
    return pow(x, mod - 2);
}
void swap(ll & a, ll & b) {
    a ^= b ^= a ^= b;
}
vector < ll > __Poly_rev[27], __Poly_power_of_g[27], __Poly_power_of_inv_g[27];
void get_rev(int len) {
    if (__Poly_rev[len].empty()) {
        __Poly_rev[len].resize(1 << len);
        __Poly_rev[len][0] = 0;
        for (int i = 0; i < (1 << len); i++) {
            __Poly_rev[len][i] = (__Poly_rev[len][i >> 1] >> 1) | ((i & 1) << (len - 1));
        }
    }
}
void get_power_of_g(int len) {
    if (__Poly_power_of_g[len].empty()) {
        __Poly_power_of_g[len].resize(1 << len);
        __Poly_power_of_inv_g[len].resize(1 << len);
        __Poly_power_of_g[len][0] = __Poly_power_of_inv_g[len][0] = 1;
        ll w = pow(g, (mod - 1) / (1 << (len + 1))), inv_w = pow(w, mod - 2);
        for (int i = 1; i < (1 << len); i++) {
            __Poly_power_of_g[len][i] = __Poly_power_of_g[len][i - 1] * w % mod;
            __Poly_power_of_inv_g[len][i] = __Poly_power_of_inv_g[len][i - 1] * inv_w % mod;
        }
    }
}
int get_length(int n) {
    for (int i = 0; ; i++) {
        if (n <= (1 << i)) {
            return i;
        }
    }
}
class Poly {
    public:
        vector < ll > a;
        int len, n;
        Poly() {
            len = 0;
            n = 1 << len;
            a.push_back(0);
            get_rev(len);
        }
        void set_length(int len_, bool clear = false) {
            if (clear) {
                a.resize(1 << len_);
            } else {
                if (len < len_) {
                    a.insert(a.end(), (1 << len_) - (1 << len), 0);
                } else {
                    a.erase(a.begin() + (1 << len_), a.end());
                }
            }
            n = 1 << len_;
            len = len_;
            get_rev(len);
        }
        Poly(const vector < ll > & vec) {
            set_length(get_length(vec.size()), true);
            for (int i = 0; i < (int)vec.size(); i++) {
                a[i] = vec[i];
            }
        }
        ll & operator [] (const int & i) {
            return a[i];
        }
        ll operator [] (const int & i) const {
            return a[i];
        }
        void NTT(int inv) {
            for (int i = 0; i < (1 << len); i++) {
                if (__Poly_rev[len][i] < i) {
                    swap(a[i], a[__Poly_rev[len][i]]);
                }
            }
            for (int i = 0; i < len; i++) {
                get_power_of_g(i);
            }
            for (int mid = 1, logmid = 0; mid < (1 << len); mid <<= 1, logmid++) {
                for (int i = 0; i < (1 << len); i += 2 * mid) {
                    for (int j = 0; j < mid; j++) {
                        ll w;
                        if (inv != -1) {
                            w = __Poly_power_of_g[logmid][j];
                        } else {
                            w = __Poly_power_of_inv_g[logmid][j];
                        }
                        ll x = a[i + j];
                        ll y = a[i + mid + j] * w % mod;
                        a[i + j] = (x + y >= mod ? x + y - mod : x + y);
                        a[i + j + mid] = (x - y < 0 ? x - y + mod : x - y);
                    }
                }
            }
            if (inv == -1) {
                ll inv_n = pow(1 << len, mod - 2);
                for (int i = 0; i < (1 << len); i++) {
                    a[i] = a[i] * inv_n % mod;
                }
            }
        }
};
void print(const Poly & a) {
    for (int i = 0; i < a.n; i++) {
        printf("%lld ", a[i]);
    }
    putchar(10);
}
Poly set_length(const Poly & a, const int & len) {
    static Poly b;
    b = a;
    b.set_length(len);
    return b;
}
void unify_length(const Poly & a, const Poly & b, Poly & x, Poly & y, Poly & c) {
    x = a;
    x.set_length(max(a.len, b.len));
    y = b;
    y.set_length(max(a.len, b.len));
    c.set_length(max(a.len, b.len), true);
}
Poly Add(const Poly & a, const Poly & b) {
    static Poly x, y, c;
    unify_length(a, b, x, y, c);
    for (int i = 0; i < x.n; i++) {
        c[i] = (x[i] + y[i]) % mod;
    }
    return c;
}
Poly Sub(const Poly & a, const Poly & b) {
    static Poly x, y, c;
    unify_length(a, b, x, y, c);
    for (int i = 0; i < x.n; i++) {
        c[i] = (x[i] - y[i] + mod) % mod;
    }
    return c;
}
Poly Mult(const Poly & a, const ll & b) {
    static Poly c;
    c = a;
    for (int i = 0; i < c.n; i++) {
        c[i] = c[i] * b % mod;
    }
    return c;
}
Poly Mult(const ll & b, const Poly & a) {
    static Poly c;
    c = a;
    for (int i = 0; i < c.n; i++) {
        c[i] = c[i] * b % mod;
    }
    return c;
}
Poly Mult(const Poly & a, const Poly & b) {
    static Poly x, y, c;
    unify_length(a, b, x, y, c);
    x.set_length(x.len + 1);
    y.set_length(y.len + 1);
    c.set_length(c.len + 1);
    x.NTT(1);
    y.NTT(1);
    for (int i = 0; i < x.n; i++) {
        c[i] = x[i] * y[i] % mod;
    }
    c.NTT(-1);
    return c;
}
Poly MultMod(const Poly & a, const Poly & b) {
    static Poly c;
    c = Mult(a, b);
    c.set_length(c.len - 1);
    return c;
}
void Divide(const Poly & a, Poly & b, int l, int r, int log2) {
    static Poly temp1, temp2;
    if (l == r - 1) {
        if (l == 0) {
            b[0] = 1;
        }
    } else {
        int mid = (l + r) / 2;
        Divide(a, b, l, mid, log2 - 1);
        temp1.set_length(log2, true);
        for (int i = 0; i < r - l; i++) {
            temp1[i] = a[i];
        }
        temp2.set_length(log2, true);
        for (int i = l; i < mid; i++) {
            temp2[i - l] = b[i];
        }
        temp1 = Mult(temp1, temp2);
        for (int i = mid; i < r; i++) {
            b[i] = (b[i] + temp1[i - l]) % mod;
        }
        Divide(a, b, mid, r, log2 - 1);
    }
}
Poly Inverse(const Poly & a) {
    static Poly ans[2];
    ans[0].set_length(0);
    ans[0][0] = pow(a[0], mod - 2);
    for (int i = 1, t; i <= a.len; i++) {
        t = i & 1;
        ans[t] = Sub(Mult(ans[t ^ 1], 2), MultMod(Mult(ans[t ^ 1], ans[t ^ 1]), set_length(a, i)));
    }
    return ans[a.len & 1];
}
Poly Differential(const Poly & a) {
    static Poly b;
    b.set_length(a.len);
    for (int i = a.n - 1; i > 0; i--) {
        b[i - 1] = a[i] * i % mod;
    }
    return b;
}
Poly Integral(const Poly & a) {
    static Poly b;
    b.set_length(a.len);
    for (int i = 1; i < a.n; i++) {
        b[i] = a[i - 1] * pow(i, mod - 2) % mod;
    }
    return b;
}
Poly Natural_Log(const Poly & a) {
    return Integral(MultMod(Differential(a), Inverse(a)));
}
Poly Exp(const Poly & a) {
    static Poly ans[2], one;
    ans[0].set_length(0);
    ans[0][0] = 1;
    for (int i = 1, t; i <= a.len; i++) {
        t = i & 1;
        ans[t ^ 1].set_length(i);
        one.set_length(i);
        one[0] = 1;
        ans[t] = MultMod(ans[t ^ 1], Add(Sub(one, Natural_Log(ans[t ^ 1])), set_length(a, i)));
    }
    return ans[a.len & 1];
}
Poly __Power(const Poly & a, const ll & k) {
    return Exp(Mult(Natural_Log(a), k));
}
Poly Power(const Poly & a, const ll & k0, const ll & k1, const ll & k2) {
    static Poly temp, one;
    int t = -1;
    ll b;
    for (int i = 0; i < a.n; i++) {
        if (a[i] != 0) {
            t = i;
            b = a[i];
            break;
        }
    }
    if (t * k2 >= a.n || t == -1) {
        one.set_length(a.len);
        return one;
    }
    temp = a;
    for (int i = t; i < temp.n; i++) {
        temp[i - t] = temp[i];
    }
    for (int i = temp.n - t; i < temp.n; i++) {
        temp[i] = 0;
    }
    ll inv_b = pow(b, mod - 2);
    for (int i = 0; i < temp.n; i++) {
        temp[i] = temp[i] * inv_b % mod;
    }
    temp = __Power(temp, k0);
    ll b_k = pow(b, k1);
    for (int i = 0; i < temp.n; i++) {
        temp[i] = temp[i] * b_k % mod;
    }
    for (int i = temp.n - t * k0 - 1; i >= 0; i--) {
        temp[i + t * k0] = temp[i];
    }
    for (int i = 0; i < t * k0 && i < temp.n; i++) {
        temp[i] = 0;
    }
    return temp;
}
namespace Cipolla {
    namespace Random {
        ll seed = 2;
        ll rand() {
            return seed = (seed * 25214903917 + 11) & ((1LL << 48) - 1);
        }
    }
    ll w;
    struct Complex {
        ll a, b;
    };
    Complex operator * (const Complex & a, const Complex & b) {
        Complex c;
        c.a = (a.a * b.a % mod + w * a.b % mod * b.b % mod) % mod;
        c.b = (a.b * b.a % mod + a.a * b.b % mod) % mod;
        return c;
    }
    Complex pow(Complex a, ll b) {
        Complex ans;
        ans.a = 1;
        while (b != 0) {
            if ((b & 1) == 1) {
                ans = ans * a;
            }
            b /= 2;
            a = a * a;
        }
        return ans;
    }
    ll Legendre(ll n) {
        return ::pow(n, (mod - 1) / 2);
    }
    ll Solve(ll n) {
        if (n == 0) {
            return 0;
        } else {
            ll a;
            while (true) {
                a = Random::rand() % mod;
                w = (a * a % mod - n + mod) % mod;
                if (Legendre(w) == mod - 1) {
                    break;
                }
            }
            Complex res;
            res.a = a;
            res.b = 1;
            res = pow(res, (mod + 1) / 2);
            ll ans = res.a;
            if (ans < mod - ans) {
                return ans;
            } else {
                return mod - ans;
            }
        }
    }
}
Poly Sqrt(const Poly & a) {
    static Poly ans[2];
    ans[0].set_length(0);
    ans[0][0] = Cipolla::Solve(a[0]);
    for (int i = 1, t; i <= a.len; i++) {
        t = i & 1;
        ans[t] = MultMod(Add(set_length(a, i), Mult(ans[t ^ 1], ans[t ^ 1])), Inverse(Mult(2, set_length(ans[t ^ 1], i))));
    }
    return ans[a.len & 1];
}
void Div(Poly f, Poly g, Poly & q, Poly & r) {
    int n = f.a.size();
    for (int i = f.a.size() - 1; i >= 0; i--) {
        if (f[i] != 0) {
            n = i;
        }
    }
    int m = g.a.size();
    for (int i = f.a.size() - 1; i >= 0; i--) {
        if (g[i] != 0) {
            n = i;
        }
    }
    reverse(f.a.begin(), f.a.begin() + n + 1);
    reverse(g.a.begin(), g.a.begin() + m + 1);
    q = Mult(f, Inverse(set_length(g, f.len)));
    for (int i = n - m + 1; i < q.n; i++) {
        q[i] = 0;
    }
    r = Sub(f, Mult(g, q));
    for (int i = 0; i <= m - 1; i++) {
        r[i] = r[i + n - m + 1];
    }
    for (int i = m; i < r.n; i++) {
        r[i] = 0;
    }
    reverse(q.a.begin(), q.a.begin() + (n - m) + 1);
    reverse(r.a.begin(), r.a.begin() + (m - 1) + 1);
}
Poly sin(const Poly & a) {
    static Poly exp_ia;
    exp_ia = Exp(Mult(a, sqrt_1));
    return Mult(Sub(exp_ia, Inverse(exp_ia)), inv2 * inv_sqrt_1 % mod);
}
Poly cos(const Poly & a) {
    static Poly exp_ia;
    exp_ia = Exp(Mult(a, sqrt_1));
    return Mult(Add(exp_ia, Inverse(exp_ia)), inv2);
}
Poly arcsin(const Poly & a) {
    static Poly one;
    one.set_length(a.len);
    one[0] = 1;
    return Integral(MultMod(Differential(a), Inverse(Sqrt(Sub(one, MultMod(a, a))))));
}
Poly arctan(const Poly & a) {
    static Poly one;
    one.set_length(a.len);
    one[0] = 1;
    return Integral(MultMod(Differential(a), Inverse(Add(one, MultMod(a, a)))));
}
struct PolyY {
    vector < ll > vec;
    int len1, len2;
    PolyY() {
        len1 = len2 = 0;
        vec.push_back(0);
    }
    ll & operator () (const int & i, const int & j) {
        return vec[(i << len2) + j];
    }
    ll operator () (const int & i, const int & j) const {
        return vec[(i << len2) + j];
    }
    void set_length(int l1, int l2, bool clear = false) {
        if (clear) {
            vec = vector < ll > (1 << (l1 + l2), 0);
        } else {
            vector < ll > new_vec(1 << (l1 + l2), 0);
            for (int i = 0; i < (1 << l1); i++) {
                for (int j = 0; j < (1 << l2); j++) {
                    if (i < (1 << len1) && j < (1 << len2)) {
                        new_vec[(i << l2) + j] = vec[(i << len2) + j];
                    }
                }
            }
            vec = new_vec;
        }
        len1 = l1;
        len2 = l2;
    }
    PolyY(int l1, int l2, const vector < ll > & a) {
        set_length(l1, l2, true);
        vec = a;
    }
    void NTT(int inv) {
        const int len = len1 + len2;
        get_rev(len);
        for (int i = 0; i < (1 << len); i++) {
            if (__Poly_rev[len][i] < i) {
                swap(vec[i], vec[__Poly_rev[len][i]]);
            }
        }
        for (int i = 0; i < len; i++) {
            get_power_of_g(i);
        }
        for (int mid = 1, logmid = 0; mid < (1 << len); mid <<= 1, logmid++) {
            for (int i = 0; i < (1 << len); i += 2 * mid) {
                for (int j = 0; j < mid; j++) {
                    ll w;
                    if (inv != -1) {
                        w = __Poly_power_of_g[logmid][j];
                    } else {
                        w = __Poly_power_of_inv_g[logmid][j];
                    }
                    ll x = vec[i + j];
                    ll y = vec[i + mid + j] * w % mod;
                    vec[i + j] = (x + y >= mod ? x + y - mod : x + y);
                    vec[i + mid + j] = (x - y < 0 ? x - y + mod : x - y);
                }
            }
        }
        if (inv == -1) {
            ll inv_n = pow(1 << len, mod - 2);
            for (int i = 0; i < (1 << len); i++) {
                vec[i] = vec[i] * inv_n % mod;
            }
        }
    }
};
void print(const PolyY & poly) {
    int n = 1 << poly.len1, m = 1 << poly.len2;
    printf("(x: %d y: %d)\n", n, m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            const ll x = poly.vec[i * m + j];
            printf("%lld ", x);
        }
        printf("\n");
    }
}
PolyY read() {
    int n, m;
    scanf("%d %d", &n, &m);
    PolyY F;
    F.set_length(get_length(n + 1), get_length(m + 1));
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            scanf("%lld", &F(i, j));
        }
    }
    return F;
}
PolyY MultMod(PolyY A, PolyY B) {
    A.NTT(1);
    B.NTT(1);
    for (int i = 0; i < (1 << (A.len1 + A.len2)); i++) {
        A.vec[i] = A.vec[i] * B.vec[i] % mod;
    }
    A.NTT(-1);
    return A;
}
Poly BostanMori(int n, PolyY U, PolyY V) {
    if (n == 0) {
        return MultMod(U.vec, Inverse(V.vec));
    } else {
        U.set_length(U.len1 + 1, U.len2 + 1);
        V.set_length(V.len1 + 1, V.len2 + 1);
        PolyY V_prime = V;
        for (int i = 1; i < (1 << V_prime.len1); i += 2) {
            for (int j = 0; j < (1 << V_prime.len2); j++) {
                if (V_prime(i, j) != 0) {
                    V_prime(i, j) = mod - V_prime(i, j);
                }
            }
        }
        V_prime.NTT(1);
        U.NTT(1);
        for (int i = 0; i < (1 << (U.len1 + U.len2)); i++) {
            U.vec[i] = U.vec[i] * V_prime.vec[i] % mod;
        }
        U.NTT(-1);
        PolyY U_;
        U_.set_length(U.len1 - 2, U.len2);
        for (int i = 0; i < (1 << U_.len1); i++) {
            for (int j = 0; j < (1 << U_.len2); j++) {
                U_(i, j) = U(2 * i + n % 2, j);
            }
        }
        V.NTT(1);
        for (int i = 0; i < (1 << (U.len1 + U.len2)); i++) {
            V.vec[i] = V.vec[i] * V_prime.vec[i] % mod;
        }
        V.NTT(-1);
        V_prime.set_length(V.len1 - 2, V.len2);
        for (int i = 0; i < (1 << V_prime.len1); i++) {
            for (int j = 0; j < (1 << V_prime.len2); j++) {
                V_prime(i, j) = V(2 * i, j);
            }
        }
        return BostanMori(n / 2, U_, V_prime);
    }
}
PolyY extract(const PolyY & a, int odd) {
    PolyY res;
    res.set_length(a.len1 - 1, a.len2);
    for (int i = 0; i < (1 << res.len1); i++) {
        for (int j = 0; j < (1 << res.len2); j++) {
            res(i, j) = a(2 * i + odd, j);
        }
    }
    return res;
}
Poly MultModT(Poly A, Poly B) {
    A.set_length(A.len + 1);
    B.set_length(B.len + 1);
    A.NTT(-1);
    B.NTT(1);
    for (int i = 0; i < A.n; i++) {
        A[i] = A[i] * B[i] % mod;
    }
    A.NTT(1);
    A.set_length(A.len - 1);
    return A;
}
PolyY MultModT(PolyY A, PolyY B) {
    A.set_length(A.len1 + 1, A.len2 + 1);
    B.set_length(B.len1 + 1, B.len2 + 1);
    A.NTT(-1);
    B.NTT(1);
    for (int i = 0; i < (1 << (A.len1 + A.len2)); i++) {
        A.vec[i] = A.vec[i] * B.vec[i] % mod;
    }
    A.NTT(1);
    A.set_length(A.len1 - 1, A.len2 - 1);
    return A;
}
PolyY set_length(PolyY a, int len1, int len2) {
    a.set_length(len1, len2);
    return a;
}
PolyY BostanMoriT(int n, PolyY U, PolyY V) {
    int l1 = V.len1, l2 = V.len2;
    if (n == 0) {
        return PolyY(l1, l2, MultModT(U.vec, Inverse(V.vec)).a);
    } else {
        int l1 = V.len1, l2 = V.len2;
        PolyY V_prime = V;
        for (int i = 0; i < (1 << l1); i++) {
            for (int j = 0; j < (1 << l2); j++) {
                if (i % 2 == 1 && V(i, j) != 0) {
                    V_prime(i, j) = mod - V(i, j);
                }
            }
        }
        V_prime.set_length(l1 + 1, l2 + 1);
        V.set_length(l1 + 1, l2 + 1);
        V.NTT(1);
        V_prime.NTT(1);
        for (int i = 0; i < (1 << (l1 + l2 + 2)); i++) {
            V.vec[i] = V.vec[i] * V_prime.vec[i] % mod;
        }
        V.NTT(-1);
        for (int i = 0; i < (1 << (l1 - 1)); i++) {
            for (int j = 0; j < (1 << (l2 + 1)); j++) {
                V(i, j) = V(2 * i, j);
            }
        }
        V.set_length(l1 - 1, l2 + 1);
        U = BostanMoriT(n / 2, U, V);
        PolyY temp;
        temp.set_length(l1, l2);
        for (int i = 0; i < (1 << (l1 - 1)); i++) {
            for (int j = 0; j < (1 << l2); j++) {
                temp(2 * i + n % 2, j) = U(i, j);
            }
        }
        temp.set_length(l1 + 1, l2 + 1);
        temp.NTT(-1);
        for (int i = 0; i < (1 << (l1 + l2 + 2)); i++) {
            temp.vec[i] = temp.vec[i] * V_prime.vec[i] % mod;
        }
        temp.NTT(1);
        temp.set_length(l1, l2);
        return temp;
    }
}
int main() {
    Poly F, G;
    int n, m;
    scanf("%d %d", &n, &m);
    n++;
    m++;
    G.set_length(get_length(n));
    for (int i = 0; i < n; i++) {
        scanf("%lld", &G[i]);
    }
    F.set_length(get_length(m));
    for (int i = 0; i < m; i++) {
        scanf("%lld", &F[i]);
    }
    PolyY P;
    P.set_length(0, get_length(n) + 1);
    for (int i = 0; i < n; i++) {
        P(0, i) = G[i];
    }
    PolyY V;
    V.set_length(get_length(n), 1);
    V(0, 0) = 1;
    for (int i = 0; i < m; i++) {
        if (F[i] != 0) {
            V(i, 1) = mod - F[i];
        }
    }
    PolyY ans = BostanMoriT(n - 1, P, V);
    for (int i = n - 1; i >= 0; i--) {
        printf("%lld ", ans(i, 0));
    }
    return 0;
}