多项式合集

 1 #include<bits/stdc++.h>
 2 #define pb push_back
 3 #define mp make_pair
 4 #define fi first
 5 #define se second
 6 #define ls (x<<1)
 7 #define rs (x<<1|1)
 8 #define db double
 9 #define all(x)  x.begin(),x.end()
10 #define ll long long
11 #define pll pair<ll,ll>
12 #define pii pair<int,int>
13 #define eps 1e-9
14 #define inf 0x3f3f3f3f
15 using namespace std;
16 const int maxn=4e5+7;
17 const int mod=1e9+7;
18 const double pi=acos(-1.0);
19 inline ll read()
20 {
21     ll x=0,f=1;char ch=getchar();
22     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
23     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
24     return x*f;
25 }
26 struct Complex
27 {
28     double x,y;
29     Complex(double xx=0,double yy=0)
30     {
31         x=xx;y=yy;
32     }
33 }A[maxn],B[maxn];
34 Complex operator+(Complex p,Complex q)
35 {
36     return Complex(p.x+q.x,p.y+q.y);
37 }
38 Complex operator*(Complex p,Complex q)
39 {
40     return Complex(p.x*q.x-p.y*q.y,p.x*q.y+p.y*q.x);
41 }
42 Complex operator-(Complex p,Complex q)
43 {
44     return Complex(p.x-q.x,p.y-q.y);
45 }
46 int lim=1,len=0;
47 int r[maxn];
48 int n;
49 char s1[maxn],s2[maxn];
50 int num[maxn];
51 void FFT(Complex* A,int op)
52 {
53     for(int i=0;i<lim;i++)
54     {
55         if(i<r[i])swap(A[i],A[r[i]]);
56     }
57     for(int j=1;j<lim;j<<=1)
58     {
59         Complex tmp(cos(pi/j),op*sin(pi/j));
60         for(int i=0;i<lim;i+=(j<<1))
61         {
62             Complex tt(1,0);
63             for(int l=0;l<j;l++,tt=tt*tmp)
64             {
65                 Complex t1=A[i+l],t2=A[i+j+l]*tt;
66                 A[i+l]=t1+t2;
67                 A[i+j+l]=t1-t2;
68             }
69         }
70     }
71 }
72 
73 int main()
74 {
75     cin>>n;
76     scanf("%s%s",s1,s2);
77     for(int i=0;i<n;i++)A[i]=s1[n-i-1]-‘0‘;
78     for(int i=0;i<n;i++)B[i]=s2[n-i-1]-‘0‘;
79     while(lim<n*2)lim<<=1,len++;
80     for(int i=0;i<=lim;i++)r[i]=(r[i>>1]>>1)|((i&1)<<(len-1));
81     FFT(A,1);FFT(B,1);
82     for(int i=0;i<=lim;i++)A[i]=A[i]*B[i];
83     FFT(A,-1);
84     for(int i=0;i<=lim;i++)num[i]=(int)(A[i].x/lim+0.5);
85     //cout<<lim<<"\n";
86     //for(int i=0;i<=lim;i++)cout<<A[i].x<<" ";cout<<"\n";
87     for(int i=0;i<lim;i++){
88         num[i+1]+=num[i]/10,num[i]%=10;
89     }
90     //cout<<num[lim]<<"\n";
91     lim++;
92     while(!num[lim]&&lim>0)lim--;
93     for(int i=lim;i>=0;i--){
94         cout<<num[i];
95     }
96 }

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ls (x<<1)
#define rs (x<<1|1)
#define db double
#define all(x)  x.begin(),x.end()
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define eps 1e-9
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=4e5+7;
const int mod=998244353;
const double pi=acos(-1.0);
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
    return x*f;
}
const int pr=3;
const int phi=mod-1;
int n,m;
int a[maxn],b[maxn],r[maxn];
int len=0;
int qpow(int a,int b)
{
    int res=1;
    while(b){
        if(b&1)res=1ll*res*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }return res;
}
void NTT(int *A,int op)
{
    for(int i=0;i<n;i++)if(i<r[i])swap(A[i],A[r[i]]);
    for(int i=1;i<n;i<<=1)
    {
        int W=qpow(pr,phi/(i<<1));
        for(int p=(i<<1),j=0;j<n;j+=p)
        {
            int w=1;
            for(int k=0;k<i;k++,w=1ll*w*W%mod)
            {
                int x=A[j+k],y=1ll*w*A[j+i+k]%mod;
                A[j+k]=(x+y)%mod;
                A[j+i+k]=(x-y+mod)%mod;
            }
        }
    }
    if(op==-1)reverse(A+1,A+n);
}
int main()
{
    cin>>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]);
    m+=n;
    n=1;
    while(n<=m)n<<=1,len++;
    for(int i=0;i<n;i++)r[i]=(r[i>>1]>>1)|((i&1)<<(len-1));
    //cout<<n<<"\n";
    NTT(a,1);NTT(b,1);
    for(int i=0;i<n;i++)a[i]=1ll*a[i]*b[i]%mod;
    //
    NTT(a,-1);//for(int i=0;i<n;i++)cout<<a[i]<<" ";cout<<"\n";
    int inv=qpow(n,mod-2);
    for(int i=0;i<n;i++)a[i]=1ll*a[i]*inv%mod;
    for(int i=0;i<m-1;i++)printf("%d ",a[i]);printf("\n");
}