多项式开根求卡常

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
const int N = 1e6+5;
namespace poly{
	const int P = 998244353, G = 3, Gi = 332748118;
	int qpow(int a, int b, int p){
		int res = 1;
		while (b){
			if (b & 1) res = res * a % p;
			a = a * a % p;
			b >>= 1;
		}
		return res;
	}
	int lim, L, rev[N];
	void NTT(int *f, int g){
		for (int i = 0;i < lim;i++) if (i < rev[i]) swap(f[i], f[rev[i]]);
		for (int len = 1;len < lim;len <<= 1){
			int wn = qpow(g, (P - 1) / (len << 1), P);
			for (int i = 0;i < lim;i += (len << 1)){
				for (int j = 0, w = 1;j < len;j++, w = w * wn % P){
					int x = f[i + j], y = w * f[i + j + len] % P;
					f[i + j] = (x + y) % P;
					f[i + j + len] = (x - y + P) % P;
				}
			}
		}
	}
	void Mul(int n, int m, int *f, int *g, int *c){
		for (lim = 1, L = 0;lim <= n + m;lim <<= 1, ++L) ;
		for (int i = 0;i < lim;i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << L - 1);
		NTT(f, G), NTT(g, G);
		for (int i = 0;i < lim;i++) f[i] = f[i] * g[i] % P;
		NTT(f, Gi);
		int inv = qpow(lim, P - 2, P);
		for (int i = 0;i <= n + m;i++) c[i] = f[i] * inv % P;
	}
	void Pow2(int n, int *f, int *c){
		for (lim = 1, L = 0;lim <= n << 1;lim <<= 1, ++L) ;
		for (int i = 0;i < lim;i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << L - 1);
		NTT(f, G);
		for (int i = 0;i < lim;i++) f[i] = f[i] * f[i] % P;
		NTT(f, Gi);
		int inv = qpow(lim, P - 2, P);
		for (int i = 0;i <= n << 1;i++) c[i] = f[i] * inv % P;
	}
	void Inv(int n, int *F, int *c){
		static int a[N], f[N];
		a[0] = qpow(F[0], P - 2, P), a[1] = 0;
		for (int b = 2;(b >> 1) <= n;b <<= 1){
			for (int i = 0;i < b;i++) f[i] = F[i];
			for (int i = b;i < b << 1;i++) f[i] = 0;
			Pow2((b >> 1) - 1, a, a);
			Mul(b - 1, b - 2, f, a, a);
			for (int i = b >> 1;i < b;i++) a[i] = (P - a[i]) % P;
			for (int i = b;i < b << 1;i++) a[i] = 0;
		}
		for (int i = 0;i <= n;i++) c[i] = a[i];
		for (int i = n + 1;i < lim;i++) c[i] = 0;
		for (int i = 0;i < lim;i++) a[i] = f[i] = 0;
	}
	void Ln(int n, int *f, int *c){
		static int a[N], b[N];
		for (int i = 1;i <= n;i++) a[i - 1] = f[i] * i % P;
		Inv(n, f, b);
		Mul(n, n, a, b, c);
		for (int i = n;i;i--) c[i] = c[i - 1] * qpow(i, P - 2, P) % P;
		c[0] = 0;
		for (int i = n + 1;i < lim;i++) c[i] = 0; 
		for (int i = 0;i < lim;i++) a[i] = b[i] = 0;
	}
	void Exp(int n, int *f, int *g){
		if (n == 0) return g[0] = 1, void();
		Exp(n >> 1, f, g);
		static int a[N], b[N];
		Ln(n, g, a);
		for (lim = 1, L = 0;lim <= n << 1;lim <<= 1, ++L) ;
		for (int i = 0;i < lim;i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << L - 1);
		for (int i = 0;i <= n;i++) b[i] = f[i];
		for (int i = n + 1;i < lim;i++) a[i] = b[i] = 0;
		for (int i = 0;i < lim;i++) b[i] = (b[i] - a[i] + P) % P;
		++b[0];
		NTT(g, G), NTT(b, G);
		for (int i = 0;i < lim;i++) g[i] = g[i] * b[i] % P, a[i] = b[i] = 0;
		NTT(g, Gi);
		int inv = qpow(lim, P - 2, P);
		for (int i = 0;i < lim;i++) g[i] = g[i] * inv % P;
		for (int i = n + 1;i < lim;i++) g[i] = 0;
	}
	void Pow(int n, int *f, ll k){
		static int g[N];
		Ln(n, f, g);
		for (int i = 0;i <= n;i++) g[i] = g[i] * k % P, f[i] = 0;
		Exp(n, g, f);
	}
    void iPow(int n, int *f, int k){
        static int g[N];
		Ln(n, f, g);
        int t = qpow(k, P - 2, P);
		for (int i = 0;i <= n;i++) g[i] = g[i] * t % P, f[i] = 0;
		Exp(n, g, f);
    }
/*
n shi duo xiang shi ci shu
Exp qian gei g qing 0
*/
}
using poly::P;
int c, n;
ll a[N], b[N];
namespace sub_1{
    void solve(){
        for (int i = 1;i <= n;i++) cout << a[i] + b[i] << ' ';
    }
}
namespace sub_2{
    void solve(){
        for (int i = 1;i <= n;i++) cout << a[i] - b[i] << ' ';
    }
}
namespace sub_3{
    void solve(){
        for (int i = 1;i <= n;i++){
            cout << (a[i] ^ b[i]) << ' ';
        }
    }
}
namespace sub_4{
    void solve(){
        for (int i = 1;i <= n;i++){
            cout << (a[i] | b[i]) << ' ';
        }
    }
}
namespace sub_5{
    void solve(){
        for (int i = 1;i <= n;i++){
            cout << (a[i] & b[i]) << ' ';
        }
    }
}
namespace sub_6{
    int F[N], G[N], H[N];
    void solve(){
        --n;
        for (int i = 0;i <= n;i++) F[i] = a[i + 1];
        for (int i = 0;i <= n;i++) G[i] = b[i + 1];
        for (int i = 0;i <= n;i++) F[i] = (F[i] + P) % P;
		for (int i = 0;i <= n;i++) G[i] = (G[i] + P) % P;
        poly::Mul(n, n, F, G, H);
        for (int i = 0;i <= 2 * n;i++) cout << H[i] << ' ';
    }
}
namespace sub_7{
    int F[N], G[N], H[N], L[N];
    void solve(){
        for (int i = 0;i < n;i++) F[i] = a[i + 1];
        for (int i = 0;i < n;i++) G[i] = b[i + 1];
        for (int i = 0;i < n;i++) F[i] = (F[i] % P + P) % P;
		for (int i = 0;i < n;i++) G[i] = (G[i] % P + P) % P;
        n = n * 2 - 1 ;
        poly::Inv(n, G, H);
        poly::Mul(n, n, F, H, L);
        for (int i = 0;i <= n;i++) cout << L[i] << ' ';
    }
}
namespace sub_8{
    int F[N], G[N], H[N];
    void solve(){
        for (int i = 0;i < n;i++) F[i] = a[i + 1];
        for (int i = 0;i < n;i++) F[i] = (F[i] % P + P) % P;
        n = n * 2 - 1 ;
        poly::iPow(n, F, 3);
        for (int i = 0;i <= n;i++) cout << F[i] << ' ';
    }
}
namespace sub_9{
    void solve(){
        for (int i = 1;i <= n;i++) cout << a[b[i]] << ' ';
    }
}
namespace sub_10{
    void solve(){
        for (int i = 1;i <= n;i++) b[i] = i  ;
        sort(b + 1 , b + 1 + n , [&] ( int x , int y) {return a[x] == a[y] ? x < y : a[x] < a[y] ; } ) ;
        for (int i = 1;i <= n;i++) cout << b[i] << ' ' ;
    }
}
namespace sub_11{
	pair<int, int> qq[N];
	void solve(){
		for (int i = 1;i <= n;i++) qq[i] = {a[i], i};
		sort(qq + 1, qq + 1 + n);
		for (int i = 1;i <= n;i++) a[qq[i].second] = i;
		for (int i = 1;i <= n;i++) cout << a[i] << ' ';
	}
}
namespace sub_12{
	void solve(){
        cout << "62652476986945811929574508085753525213325243476748757638370409819051066331429819908604545880040736669362770937694609989560289409637253984209373160098134477290043961183590474128343974265063328000"; 
	}
}
namespace sub_13{
	void solve(){
        double ans = 0;
        for (int i = 2;i <= n;i++){
            double x = (a[i] - a[i - 1]) , y = b[i] - b[i - 1];
            ans += sqrt(x * x + y * y);
        }
        cout << fixed << setprecision(2) << ans;
    }
}
namespace sub_14{
    double avx;
	void solve(){
        for (int i = 1;i <= n;i++){
            avx += a[i] - b[i];
        }
        avx /= n;
        double sum = 0;
        for (int i = 1;i <= n;i++){
            sum += (avx - a[i] + b[i]) * (avx - a[i] + b[i]);
        }
        sum /= n;
        cout << fixed << setprecision(2) << sum ; 
    }
}
namespace sub_15{
    double x[N], y[N], m, sxy, sx, sy, sx2, sy2;
	void solve(){
        for (int i = 1;i <= n;i++){
            x[i] = a[i], y[i] = b[i];
            sxy += x[i] * y[i];
            sx += x[i];
            sy += y[i];
            sx2 += x[i] * x[i];
            sy2 += y[i] * y[i];
        }
        m = (n * sxy - sx * sy) / (n * sx2 - sx * sx);
        double k;
        k = (sy - m * sx) / n;
        cout << "k=" << fixed << setprecision(2) << m << ' ';
        cout << "b=" << fixed << setprecision(2) << k;
    }
}
namespace sub_16{
	bool vis[5002][5002];
	void solve(){
		ll mx = 0;
		for (int i = 1;i <= n;i++){
			vis[a[i]][b[i]] = 1;
			mx = max(mx, a[i]);
			mx = max(mx, b[i]);
		}
		for (int i = 0;i <= mx;i++){
			for (int j = 0;j <= mx;j++){
				cout << vis[i][j] << ' ';
			}
			cout << '\n';
		}
	}
}
namespace sub_17{
    #define db double
    struct node{
        db x,y;
        inline const bool operator<(const node &p)const{
            return x==p.x?y<p.y:x<p.x;
        }
        inline const node operator-(const node p)const{
            return node{x-p.x,y-p.y};
        }
        inline const db operator *(const node p)const{
            return y*p.x-x*p.y;
        }
    }p[N],ans[N];
    int stk[N],tp,cnt;
    bool used[N];
    db anser;
    inline db dis(node p,node q){
        return sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y));
    }
    db sqr(node a, node b, node c){
        double l1, l2, l3;
        l1 = dis(a, b);
        l2 = dis(b, c);
        l3 = dis(a, c);
        double p = (l1 + l2 + l3) / 2;
        double S = p * (p - l1) * (p - l2) * (p - l3);
        return sqrt(S);
    }
	void solve(){
        for (int i = 1;i <= n;i++) p[i].x = a[i];
        for (int i = 1;i <= n;i++) p[i].y = b[i];
		sort(p+1,p+1+n);
        stk[++tp]=1;
        for(int i=2;i<=n;i++){
            while(tp>1 and (p[stk[tp]]-p[stk[tp-1]])*(p[i]-p[stk[tp-1]])<=0)used[stk[tp--]]=0;
            stk[++tp]=i;used[i]=1;
        }
        int tmp=tp;
        for(int i=n-1;i;i--){
            if(!used[i]){
                while(tp>tmp and (p[stk[tp]]-p[stk[tp-1]])*(p[i]-p[stk[tp-1]])<=0)used[stk[tp--]]=0;
                used[i]=1;
                stk[++tp]=i;
            }
        }
        cnt=tp; cnt -- ;
        for(int i=1;i<=cnt;i++)ans[i]=p[stk[i]];
        double Z = 0 ; 
        for (int j = 2;j < cnt ; j++ ) {
            Z += sqr(ans[1] , ans[j] , ans[j + 1] ) ; 
        }
        cout << fixed << setprecision(2) << Z;
	}
}
namespace sub_18{
    int F[N], G[N], H[N];
    void solve(){
        for (int i = 0;i < n;i++) F[i] = a[i + 1];
        for (int i = 0;i < n;i++) F[i] = (F[i] % P + P) % P;
        n = n * 2 - 1 ;
        poly::iPow(n, F, 2);
        for (int i = 0;i <= n;i++) cout << F[i] << ' ';
    }
}
namespace sub_19{
	void solve(){
		ll sa = 0;
		for (int i = 1;i <= n;i++) sa ^= a[i] ^ b[i];
		if (sa > 0) cout << "Win!";
		else cout << "Lose!";
	}
}
namespace sub_20{
	void solve(){
		for (int i = 1;i <= n;i++) cout << a[i] << ' ';
		for (int i = 1;i <= n;i++) cout << b[i] << ' ';
	}
}
namespace tianyu{
	void awa(){
		cin >> c >> n;
		for (int i = 1;i <= n;i++) cin >> a[i];
		for (int i = 1;i <= n;i++) cin >> b[i];
        if (c == 1) sub_1::solve();
        if (c == 2) sub_2::solve();
        if (c == 3) sub_3::solve();
        if (c == 4) sub_4::solve();
        if (c == 5) sub_5::solve();
        if (c == 6) sub_6::solve();
        if (c == 7) sub_7::solve();
        if (c == 8) sub_8::solve();
        if (c == 9) sub_9::solve();
        if (c == 10) sub_10::solve();
		if (c == 11) sub_11::solve();
        if (c == 12) sub_12::solve();
        if (c == 13) sub_13::solve();
        if (c == 14) sub_14::solve();
        if (c == 15) sub_15::solve();
		if (c == 16) sub_16::solve();
        if (c == 17) sub_17::solve();
        if (c == 18) sub_18::solve();
		if (c == 19) sub_19::solve();
		if (c == 20) sub_20::solve();
	}
}
signed main(){
    cin.tie(0)->sync_with_stdio(false);
    // freopen("game.in", "r", stdin);
    // freopen("game.out", "w", stdout);
	int T = 1;
	while (T--) tianyu::awa();
	return 0;
}