多项式除法

概述

我们知道对于多项式$A$和多项式$B$，有唯一的$Q$和$R$使得$A=QB+R$，其中$\deg R < \deg B$。

多项式除法就是给定$A$和$B$，求$Q$和$R$。

求法

参考miskcoo大佬的博客

已知
$$
A(x)=Q(x)B(x)+R(x)
$$
其中$n=\deg A$，$m=\deg B$，且$m\leqslant n$。那么两边乘$x^n$就有
$$
x^nA(\frac{1}{x})=x^{n-m}Q(\frac{1}{x})x^mB(\frac{1}{x})+x^{n-m+1}x^{m-1}R(\frac{1}{x})
$$
而如果$\deg A=n$，那么$x^nA(\frac{1}{x})$就表示翻转系数（可以举个例子感受一下），可以记做$A^R(x)$。

而我们发现$\deg R \leqslant m-1$，如果$R$不足$m-1$次，就在高位补$0$。而同样的$Q$也可以这样。

所以上式可以写作：
$$
A^R(x)=Q^R(x)B^R(x)+x^{n-m+1}R^R(x)
$$
两边对$x^{n-m+1}$取模也没有影响：
$$
A^R(x)\equiv Q^R(x)B^R(x)(\mod x^{n-m+1})
$$
然后我们对$B^R$求逆就可以求出$Q^R$，翻转后回代即可。

参考程序

#include <bits/stdc++.h>
#define LL long long
using namespace std;

const LL Mod = 998244353;
const LL MaxN = 400010;
LL N, M, Q[ MaxN ], R[ MaxN ], F[ MaxN ], G[ MaxN ];

void Read() {
    scanf( "%lld%lld", &N, &M );
    ++N; ++M;
    for( LL i = 0; i < N; ++i ) scanf( "%lld", &F[ i ] );
    for( LL i = 0; i < M; ++i ) scanf( "%lld", &G[ i ] );
    return;
}

void Print() {
    for( LL i = 0; i < N - M + 1; ++i ) printf( "%lld ", Q[ i ] ); printf( "\n" );
    for( LL i = 0; i < M - 1; ++i ) printf( "%lld ", R[ i ] ); printf( "\n" );
    return;
}

LL FastPow( LL x, LL y ) {
    LL Ans = 1;
    for( ; y; y >>= 1, x = x * x % Mod )
        if( y & 1 )
            Ans = Ans * x % Mod;
    return Ans;
}

namespace Polynom {

    LL n, Index[ MaxN ], Omega[ MaxN ], InvOmega[ MaxN ];
    LL A[ MaxN ], B[ MaxN ], InvB[ MaxN ], Mul[ MaxN ];
    LL a[ MaxN ], b[ MaxN ];

    void Init( LL N ) {
        for( n = 1; n < N << 1; n <<= 1 );
        Omega[ 0 ] = 1; Omega[ 1 ] = FastPow( 3, ( Mod - 1 ) / n );
        for( LL i = 2; i < n; ++i ) Omega[ i ] = Omega[ i - 1 ] * Omega[ 1 ] % Mod;
        InvOmega[ n - 1 ] = FastPow( Omega[ n - 1 ], Mod - 2 );
        for( LL i = n - 2; i >= 0; --i ) InvOmega[ i ] = InvOmega[ i + 1 ] * Omega[ 1 ] % Mod;
        return;
    }

    void Reverse( LL *A, LL Len ) {
        for( LL i = 0; i + i < Len; ++i )
            swap( A[ i ], A[ Len - i - 1 ] );
        return;
    }

    void NTT( LL L, LL *A, LL *Omega ) {
        for( LL i = 0; i < L; ++i )
            Index[ i ] = ( Index[ i >> 1 ] >> 1 ) | ( ( i & 1 ) * ( L >> 1 ) );
        for( LL i = 0; i < L; ++i )
            if( i < Index[ i ] )
                swap( A[ i ], A[ Index[ i ] ] );
        for( LL HalfLen = 1; HalfLen < L; HalfLen <<= 1 )
            for( LL i = 0; i < L; i += HalfLen << 1 ) 
                for( LL j = 0; j < HalfLen; ++j ) {
                    LL T = Omega[ n / 2 / HalfLen * j ] * A[ i + j + HalfLen ] % Mod;
                    LL t = A[ i + j ];
                    A[ i + j ] = ( t + T ) % Mod;
                    A[ i + j + HalfLen ] = ( t - T + Mod ) % Mod;
                }
        return;
    }

    void Inverse( LL Len, LL *A, LL *Ans ) {
        if( Len == 1 ) {
            Ans[ 0 ] = FastPow( A[ 0 ], Mod - 2 );
            return;
        }
        Inverse( ( Len + 1 ) >> 1, A, Ans );
        LL len = 1;
        for( ; len < Len << 1; len <<= 1 );
        memset( a, 0, sizeof( a ) );
        memset( b, 0, sizeof( b ) );
        for( LL i = 0; i < Len; ++i ) a[ i ] = A[ i ];
        for( LL i = 0; i < Len; ++i ) b[ i ] = Ans[ i ];
        NTT( len, a, Omega );
        NTT( len, b, Omega );
        for( LL i = 0; i < len; ++i ) {
            b[ i ] = b[ i ] * ( 2 - a[ i ] * b[ i ] % Mod ) % Mod;
            b[ i ] = ( b[ i ] + Mod ) % Mod;
        }
        NTT( len, b, InvOmega );
        LL Inv = FastPow( len, Mod - 2 );
        for( LL i = 0; i < len; ++i )
            b[ i ] = b[ i ] * Inv % Mod;
        for( LL i = Len; i < len; ++i ) b[ i ] = 0;
        memcpy( Ans, b, sizeof( b ) );
        return;
    }

    void Multiply( LL Len, LL *A, LL *B, LL *Ans ) {
        LL len = 1;
        for( ; len < Len << 1; len <<= 1 );
        NTT( len, A, Omega ); NTT( len, B, Omega );
        for( LL i = 0; i < len; ++i ) Ans[ i ] = A[ i ] * B[ i ] % Mod;
        NTT( len, Ans, InvOmega );
        LL Inv = FastPow( len, Mod - 2 );
        for( LL i = 0; i < len; ++i ) Ans[ i ] = Ans[ i ] * Inv % Mod;
        return;
    }

    void Division( LL N, LL M, LL *F, LL *G, LL *Q, LL *R ) {
        LL ModuleLen = N - M + 1;
        memset( A, 0, sizeof( A ) );
        memset( B, 0, sizeof( B ) );
        for( LL i = 0; i < N; ++i ) A[ i ] = F[ i ];
        for( LL i = 0; i < M; ++i ) B[ i ] = G[ i ];
        Reverse( A, N );
        Reverse( B, M );
        for( LL i = ModuleLen; i < N; ++i ) A[ i ] = 0;
        for( LL i = ModuleLen; i < M; ++i ) B[ i ] = 0;
        Inverse( ModuleLen, B, InvB );
        Multiply( ModuleLen, A, InvB, Q );
        Reverse( Q, N - M + 1 );
        memset( A, 0, sizeof( A ) );
        memset( B, 0, sizeof( B ) );
        for( LL i = 0; i < N; ++i ) A[ i ] = G[ i ];
        for( LL i = 0; i < N - M + 1; ++i ) B[ i ] = Q[ i ];
        Multiply( N, A, B, Mul );
        for( LL i = 0; i < M; ++i ) R[ i ] = ( F[ i ] - Mul[ i ] + Mod ) % Mod;
        return;
    }
} //Polynom

int main() {
    Read();
    Polynom::Init( N );
    Polynom::Division( N, M, F, G, Q, R );
    Print();
    return 0;
}