多项式除法模板
$LuoguP4512$
————————————————-
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
#include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #define mo 998244353 #define G 3 #define ll long long using namespace std; const int N=300010; int n,m,a[N],b[N],w[N],L,INV; ll mi(ll x,int y) { ll ans=1; while (y) { if (y&1) ans=ans*x%mo; x=x*x%mo; y>>=1; } return ans; } void NTT(int *A,int f) { for (int i=0,j=0;i<L;i++) { if (i>j) swap(A[i],A[j]); for (int k=L>>1;(j^=k)<k;k>>=1); } for (int len=2;len<=L;len<<=1) { int l=len>>1; int W=mi(G,(mo-1)/len); for (int i=1;i<l;i++) w[i]=(ll)w[i-1]*W%mo; for (int i=0;i<L;i+=len) for (int j=0;j<l;j++) { int x=A[i+j],y=(ll)A[i+j+l]*w[j]%mo; A[i+j]=(x+y)%mo; A[i+j+l]=(x-y+mo)%mo; } } if (f==-1) { for (int i=1;i<L/2;i++) swap(A[i],A[L-i]); for (int i=0;i<L;i++) A[i]=(ll)A[i]*INV%mo; } } void pre(int l) { L=1; while (L<l) L<<=1; INV=mi(L,mo-2); w[0]=1; } void Get_INV(int *A,int n,int *B) { if (n==1) { B[0]=mi(A[0],mo-2);return;} Get_INV(A,n>>1,B); pre(n*2); static int C[N]; for (int i=0;i<L;i++) C[i]=0; for (int i=0;i<n;i++) C[i]=A[i]; NTT(C,1);NTT(B,1); for (int i=0;i<L;i++) B[i]=((B[i]+B[i])%mo-(ll)C[i]*B[i]%mo*B[i]%mo+mo)%mo; NTT(B,-1); for (int i=n;i<L;i++) B[i]=0; } void Calc_INV(int *A,int n,int *B) { ll X=1; while (X<=n) X<<=1; Get_INV(A,X,B); } void mul(int *A,int *B,int *C,int l) { pre(l); NTT(A,1);NTT(B,1); for (int i=0;i<L;i++) C[i]=(ll)A[i]*B[i]%mo; NTT(B,-1);NTT(C,-1); } void division(int *A,int *B) { reverse(A,A+n); reverse(B,B+m); static int C[N],D[N]; Calc_INV(B,n-m+1,C); mul(C,A,C,n+n); for (int i=n-m+1;i<L;i++) C[i]=0; reverse(C,C+n-m+1); for (int i=0;i<=n-m;i++) printf("%d%c",C[i]," \n"[i==n-m]); pre(n+n); reverse(A,A+n); reverse(B,B+m); NTT(B,1);NTT(C,1); for (int i=0;i<L;i++) B[i]=(ll)B[i]*C[i]%mo; NTT(B,-1); for (int i=0;i<m-1;i++) D[i]=(A[i]-B[i]+mo)%mo; for (int i=0;i<m-1;i++) printf("%d%c",D[i]," \n"[i==m-2]); } int main() { scanf("%d%d",&n,&m); n++;m++; for (int i=0;i<n;i++) scanf("%d",&a[i]); for (int i=0;i<m;i++) scanf("%d",&b[i]); division(a,b); return 0; } |
