多项式板子

#include 
using namespace std;
#define ll long long
const ll N = 1e5+50;
namespace NTT{
    const int P[3] = {469762049, 998244353, 167772161},//模数
    G = 3, //原根
    Gi[3] = {P[0] / G + 1, P[1] / G + 1, P[2] / G + 1};//逆元
    int R[N];
    inline int f_pow(int x, int y) {
        int ans = 1;
        while(y) {
            if(y & 1) ans = 1ll*ans * x % P[1];
            y >>= 1; x = 1ll*x * x % P[1];
        }
        return ans%P[1];
    }
    inline void ntt(int A[],int limit,int type){
        for(int i = 0;i < limit;i++)if(i < R[i])std::swap(A[i],A[R[i]]);
        for(int mid = 1;mid < limit;mid<<=1){
            int wn = f_pow(type == 1?G:Gi[1],(P[1]-1)/(mid<<1));//原根
            // if(type == -1) wn = f_pow(wn,mod-2);
            for(int len = mid<<1,pos = 0;pos < limit;pos+=len){
                int w = 1;
                for(int k = 0;k> 1] >> 1 | ((i & 1) << (L - 1));
        ntt(a, limit, 1);ntt(b, limit, 1);
        for (int i = 0; i <= limit; i++) a[i] = 1ll*a[i] * b[i] % P[1];
        ntt(a, limit, -1);
    }
    //多项式求逆元
    inline void  inv(int a[],int b[],int n){//多项式求逆元
        static int c[N];
        if(n == 1){b[0] = f_pow(a[0],P[1]-2);return;}

        inv(a,b,(n+1)>>1);
        int limit = 1, L = 0;
        while (limit <= n+n)limit <<= 1, L++;
        for (int i = 0; i < limit; i++)R[i] = R[i >> 1] >> 1 | ((i & 1) << (L - 1));
        for(int i = 0; i < limit; ++i) {
            R[i] = (R[i >> 1] >> 1) | ((i & 1) ? (limit >> 1) : 0);
            c[i] = (i < n ? a[i] : 0);//只算到?n/2?，后面的全部为0;
        }
        ntt(c,limit,1),ntt(b,limit,1);
        for(int i = 0; i < limit; ++ i) {
            b[i] = (2ll - 1ll*c[i] * b[i] % P[1] + P[1]) % P[1] * b[i] % P[1];
        }
        ntt(b,limit,-1);
        fill(b+n,b+limit,0);
//        for(ll i = 0;i < n;i++)cout<