【템플릿】다항식 곱셈 역
제목.
https://www.luogu.com.cn/problem/P4238
사고의 방향
좋습니다. 또 하나의 다항식 이기를 배웠습니다. 이것은 대략 한 배로 증가하는 과정입니다. 즉, 먼저 A*B'=1(mod n/2)을 구하면 n에 전달할 수 있고 여기에 블로그를 추천할 수 있습니다.https://www.luogu.com.cn/problem/P4238
코드
#include
#define ll long long
using namespace std;
const int N=2e6+77;
const ll mod=998244353,g=3;
ll a[N],b[N],c[N],r[N];
int n;
ll power(ll x,ll t)
{
ll b=1;
while(t)
{
if(t&1) b=b*x%mod;
x=x*x%mod; t>>=1;
}
return b;
}
void dft(ll *a,int n,int f)
{
for(int i=0; i<n; i++) if(i<r[i]) swap(a[i],a[r[i]]);
for(int i=2; i<=n; i<<=1)
{
int now=i>>1;
ll wn=power(g,(mod-1)/i);
if(f==-1) wn=power(wn,mod-2);
for(int j=0; j<n; j+=i)
{
ll w=1,x,y;
for(int k=j; k<j+now; k++,w=w*wn%mod)
{
x=a[k],y=w*a[k+now]%mod;
a[k]=(x+y)%mod; a[k+now]=(x-y+mod)%mod;
}
}
}
ll inv=power(n,mod-2);
if(f==-1) for(int i=0; i<n; i++) a[i]=a[i]*inv%mod;
}
void work(int yjy,ll *a,ll *b)
{
if(yjy==1)
{
b[0]=power(a[0],mod-2); return;
}
work((yjy+1)>>1,a,b);
int aii=0,p=1;
while(p<(yjy<<1)) p<<=1,aii++;
for(int i=1; i<p; i++) r[i]=(r[i>>1]>>1)|((i&1)<<(aii-1));
for(int i=0; i<yjy; i++) c[i]=a[i];
for(int i=yjy; i<p; i++) c[i]=0;
dft(c,p,1),dft(b,p,1);
for(int i=0; i<p; i++) b[i]=(2-c[i]*b[i]%mod+mod)%mod*b[i]%mod;
dft(b,p,-1);
for(int i=yjy; i<p; i++) b[i]=0;
}
int main()
{
scanf("%d",&n);
for(int i=0; i<n; i++) scanf("%lld",&a[i]);
work(n,a,b);
for(int i=0; i<n; i++) printf("%lld ",b[i]);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.