CodeForces 438 E. The Child and Binary Tree(생성 함수 + FFT)
하나의 대점권유근 이차수라고 하는 것은 좋은 것이고 모든 노드의 권치가 집합 {c1, c2,...,cn}에 속할 때만 전체 나무의 권치를 모든 점의 권치의 합으로 하고 하나의 정수 m를 제시하며 각각의 s≤m에 대해 권치가 s의 좋은 이차수 개수를 구한다
Input
첫 번째 줄은 두 개의 정수 n,m를 입력하고, 그 다음에 n개의 정수ci(1≤n, m≤105, 1≤ci≤105)를 입력한다.
Output
출력 m개 정수, 각각 표시권 1,2,...,m의 좋은 두 갈래 나무 개수, 결과 모드 998244353=7 ⋅17⋅223+1
Sample Input
2 3 1 2
Sample Output
1 3 9
Solution
각 점 값의 생성 함수 A (x), 트리의 생성 함수 F (x) 설정
아들 노드가 있는 것과 아들 노드가 없는 것을 고려하면 방정식 F(x)=A(x)F2(x)+1, 이 2차 방정식을 풀면 F(x)=1±1−4A(x)≠2A(x)
1−4A(x) 개근 상수항은 1이고 A(x)에는 상수항이 없기 때문에 상수항을 없애야만 나눌 수 있음
즉 F(x)=1−1−4A(x)≠2A(x)로 풀고, 다항식 개근과 역원을 하면 된다
Code
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
#define maxn 100005
#define maxfft 262144+5
#define mod 998244353
const double pi=acos(-1.0);
struct cp
{
double a,b;
cp operator +(const cp &o)const {return (cp){a+o.a,b+o.b};}
cp operator -(const cp &o)const {return (cp){a-o.a,b-o.b};}
cp operator *(const cp &o)const {return (cp){a*o.a-b*o.b,b*o.a+a*o.b};}
cp operator *(const double &o)const {return (cp){a*o,b*o};}
cp operator !() const{return (cp){a,-b};}
}w[maxfft];
int pos[maxfft];
void fft_init(int len)
{
int j=0;
while((1<for(int i=0;ipos[i]=pos[i>>1]>>1|((i&1)<*x,int len,int sta)
{
for(int i=0;iif(i<pos[i])swap(x[i],x[pos[i]]);
w[0]=(cp){1,0};
for(unsigned i=2;i<=len;i<<=1)
{
cp g=(cp){cos(2*pi/i),sin(2*pi/i)*sta};
for(int j=i>>1;j>=0;j-=2)w[j]=w[j>>1];
for(int j=1;j>1;j+=2)w[j]=w[j-1]*g;
for(int j=0;j*a=x+j,*b=a+(i>>1);
for(int l=0;l>1;l++)
{
cp o=b[l]*w[l];
b[l]=a[l]-o;
a[l]=a[l]+o;
}
}
}
if(sta==-1)for(int i=0;ix[i].a/=len,x[i].b/=len;
}
cp x[maxfft],y[maxfft],z[maxfft];
int temp[maxfft];
void FFT(int *a,int *b,int n,int m,int *c)
{
if(n<=100&&m<=100||min(n,m)<=5)
{
for(int i=0;im-1;i++)temp[i]=0;
for(int i=0;ifor(int j=0;j<m;j++)
{
temp[i+j]+=(ll)a[i]*b[j]%mod;
if(temp[i+j]>=mod)temp[i+j]-=mod;
}
for(int i=0;im-1;i++)c[i]=temp[i];
return ;
}
int len=1;
while(lenm)len<<=1;
fft_init(len);
for(int i=0;iint aa=i0,bb=i<m?b[i]:0;
x[i]=(cp){(aa>>15),(aa&32767)},y[i]=(cp){(bb>>15),(bb&32767)};
}
fft(x,len,1),fft(y,len,1);
for(int i=0;iint j=len-1&len-i;
z[i]=((x[i]+!x[j])*(y[i]-!y[j])+(x[i]-!x[j])*(y[i]+!y[j]))*(cp){0,-0.25};
}
fft(z,len,-1);
for(int i=0;im-1;i++)
{
ll ta=(ll)(z[i].a+0.5)%mod;
ta=(ta<<15)%mod;
c[i]=ta;
}
for(int i=0;iint j=len-1&len-i;
z[i]=(x[i]-!x[j])*(y[i]-!y[j])*(cp){-0.25,0}+(x[i]+!x[j])*(y[i]+!y[j])*(cp){0,0.25};
}
fft(z,len,-1);
for(int i=0;im-1;i++)
{
ll ta=(ll)(z[i].a+0.5)%mod,tb=(ll)(z[i].b+0.5)%mod;
ta=(ta+(tb<<30))%mod;
c[i]=(c[i]+ta)%mod;
}
}
int inv[maxn];
void init(int n=100001)
{
inv[1]=1;
for(int i=2;i<=n;i++)inv[i]=mod-(ll)(mod/i)*inv[mod%i]%mod;
}
int temp1[maxfft],temp2[maxfft],temp3[maxfft],temp4[maxfft];
void Poly_Inv(int *poly,int n,int *ans)
{
ans[0]=inv[poly[0]];
for(int i=2;i<=n;i<<=1)
{
FFT(poly,ans,i,i/2,temp1);
FFT(ans,temp1+i/2,i/2,i/2,temp1);
for(int j=0;j2;j++)ans[j+i/2]=temp1[j]==0?0:mod-temp1[j];
}
}
void Poly_Log(int *poly,int n,int *ans)
{
Poly_Inv(poly,n,temp2);
for(int i=0;i1;i++)ans[i]=(ll)poly[i+1]*(i+1)%mod;
FFT(ans,temp2,n-1,n,ans);
for(int i=n-1;i>0;i--)ans[i]=(ll)ans[i-1]*inv[i]%mod;
ans[0]=0;
}
void Poly_Exp(int *poly,int n,int *ans)
{
if(n==1)
{
ans[0]=1;
return ;
}
Poly_Exp(poly,n/2,ans);
Poly_Log(ans,n,temp3);
for(int i=0;iif(temp3[i]<0)temp3[i]+=mod;
}
temp3[0]++;
if(temp3[0]==mod)temp3[0]=0;
FFT(ans,temp3,n,n,ans);
for(int i=n;i<2*n;i++)ans[i]=0;
}
void Poly_Root(int *poly,int n,int *ans)
{
ans[0]=1;
for(int i=2;i<=n;i<<=1)
{
Poly_Inv(ans,i,temp4);
FFT(ans,ans,i/2,i/2,ans);
for(int j=0;j*inv[2]%mod;
FFT(ans,temp4,i,i,ans);
for(int j=i;j<2*i;j++)ans[j]=0;
}
}
int n,m,A[maxfft],B[maxfft];
int main()
{
init();
while(~scanf("%d%d",&n,&m))
{
memset(A,0,sizeof(A));
for(int i=1;i<=n;i++)
{
int temp;
scanf("%d",&temp);
A[temp]=mod-4;
}
int len=1;
while(len<m+1)len<<=1;
A[0]=1;
Poly_Root(A,len,B);
for(int i=1;i<=m;i++)B[i]=(ll)B[i]*inv[2]%mod;
Poly_Inv(B,len,A);
for(int i=1;i<=m;i++)printf("%d
",A[i]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
CodeForces 140 E. New Year Garland(콤보 수학+dp)Description n열, i열 li 위치, 현재 모든 위치에 m가지 색깔로 색칠을 하려면 만족해야 합니다. 1. 한 줄씩 서로 인접한 위치마다 다른 색 2. 인접 배열에 사용되는 색상 세트가 다름 질문 시나리오 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.