题解：P12321 [蓝桥杯 2024 国研究生组] 生成树问题

· · 题解

思路

考虑每条满足 xy 为完全平方数的边 (x,y)，其贡献都为 1，考虑设计一种母函数区分边权为 0 和 1 带来的贡献，不妨令

f_i=\sum\limits_{1\le j < i} [\sqrt{ij} \in \mathbb Z]

即 f_i 表示小于 i 的数中与 i 相乘能得到完全平方数的数的个数。

则显然有一种母函数的设计

F(i)=f_ix+i-f_i-1

即自己不能给自己带来贡献，f_i 带来 1 的贡献，i-f_i-1 的部分带来 0 的贡献。

于是可以列出答案的母函数

F_{ans}(n)=\prod\limits_{i=2}^n F(i)

观察这个形式，由母函数的定义及基本性质可以得到

ans_i=[x^i]F_{ans}(n)

于是考虑 f 怎么求。利用惊人的注意力可以发现这是个积性函数，欧拉筛预处理即可。

我们利用分治思想和 FFT 求出 F_{ans}(n)（可能是一种分治 FFT？）。

考虑时间复杂度，利用 Master 定理，

T(n)=2T(\frac{n}{2})+O(n\log n)=O(n^{\log_22}\log^{1+1}n)=O(n\log^2n)

注意常数优化。

代码

卷积长度不要太大。

#include <bits/stdc++.h>
//#include <bits/extc++.h>
namespace fastio
{
#ifdef ONLINE_JUDGE
    namespace __getchar
    {
        char buf[1<<24],*p1=buf,*p2=buf;
        inline char getchar() {return (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2))?EOF:(*p1++);}
    }
    using __getchar::getchar;
#endif
    inline int read(int &x) {unsigned s=0;int f=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-f; ch=getchar();} while(isdigit(ch)) {s=(s<<3)+(s<<1)+(ch^48); ch=getchar();} return x=s*f;}
    inline unsigned read(unsigned &x) {unsigned s=0; char ch=getchar(); while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)) {s=(s<<3)+(s<<1)+(ch^48); ch=getchar();} return x=s;}
    inline long long read(long long &x) {unsigned long long s=0; long long f=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-f; ch=getchar();} while(isdigit(ch)) {s=(s<<3)+(s<<1)+(ch^48); ch=getchar();} return x=s*f;}
    inline unsigned long long read(unsigned long long &x) {unsigned long long s=0; char ch=getchar(); while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)) {s=(s<<3)+(s<<1)+(ch^48); ch=getchar();} return x=s;}
    inline char read(char &x) {x=getchar(); while(x=='\0'||x=='\r'||x=='\n'||x==' ') x=getchar(); return x;}
    inline int read(char *x) {int i=0; char ch=getchar(); while(ch=='\0'||ch=='\r'||ch=='\n'||ch==' ') ch=getchar(); while(ch!='\0'&&ch!='\r'&&ch!='\n'&&ch!=' '&&ch!=EOF) {x[i++]=ch; ch=getchar();} x[i]='\0'; return i;}
    inline int read(std::string &x) {x=""; int i=0; char ch=getchar(); while(ch=='\0'||ch=='\r'||ch=='\n'||ch==' ') ch=getchar(); while(ch!='\0'&&ch!='\r'&&ch!='\n'&&ch!=' '&&ch!=EOF) {x+=ch; i++; ch=getchar();} return i;}
    inline void write(int x) {if(x<0) {putchar('-'); write(0-x/10); putchar(48-x%10); return;} if(x<10) putchar(x+48); else {write(x/10); putchar(x%10+48);}}
    inline void write(unsigned x) {if(x<10) putchar(x+48); else {write(x/10); putchar(x%10+48);}}
    inline void write(long long x) {if(x<0) {putchar('-'); write(0-x/10); putchar(48-x%10); return;} if(x<10) putchar(x+48); else {write(x/10); putchar(x%10+48);}}
    inline void write(unsigned long long x) {if(x<10) putchar(x+48); else {write(x/10); putchar(x%10+48);}}
    inline void write(char x) {putchar(x);}
    inline void write(char *x) {char *tmp=x; while(*x!=EOF&&*x!='\0') putchar(*x++); x=tmp;}
    inline void write(const char *x) {while(*x!=EOF&&*x!='\0') putchar(*x++);}
    inline void write(std::string x) {for(char c:x) putchar(c);}
    template<typename _Tp,typename ...Args>
    inline void read(_Tp &x,Args &...args) {read(x); read(args...);}
    template<typename _Tp>
    inline void read(std::initializer_list<_Tp> &x) {for(auto i:x) read(i);}
    template<typename _Tp,typename ...Args>
    inline void write(_Tp x,Args ...args) {write(x); write(args...);}
    template<typename _Tp>
    inline void write(std::initializer_list<_Tp> x) {for(auto i:x) write(i);};
}
using namespace fastio;
//#define int long long
#define G 3
#define mod 998244353
#define __BEGIN_MULTITEST__ \
    signed T; \
    scanf("%d",&T); \
    while(T--) \
    {
#define __END_MULTITEST__ }
using namespace std;
//using namespace __gnu_cxx;
//using namespace __gnu_pbds;
namespace ntt
{
    inline int quick_pow(int a,int b)
    {
        int ret=1;
        while(b)
        {
            if(b&1)
                ret=1ll*ret*a%mod;
            a=1ll*a*a%mod;
            b>>=1;
        }
        return ret; 
    }
    int g[1100005],invlim[1100005];
    void initNTT(int lim)
    {
        g[0]=1;
        g[1]=quick_pow(G,(mod-1)/lim);
        for(int i=2;i<=lim;i++)
            g[i]=1ll*g[i-1]*g[1]%mod;
    }
    void initinv(int lim)
    {
        invlim[0]=invlim[1]=1;
        invlim[2]=499122177;
        for(int i=4;i<=lim;i<<=1)
            invlim[i]=1ll*invlim[i>>1]*invlim[2]%mod;
    }
    void NTT(int f[],int rev[],int lim,int type)
    {
        if(!lim) return;
        for(int i=0;i<=lim;i++)
            if(i<rev[i])
                swap(f[i],f[rev[i]]);
        for(int k=1,tmp=lim>>1;k<lim;k<<=1,tmp>>=1)
            for(int i=0;i<lim;i+=(k<<1))
                for(int j=0,s=0;j<k;j++,s+=tmp)
                {
                    int x=f[i|j],y=1ll*g[s]*f[i|j|k]%mod;
                    f[i|j]=(x+y)%mod;
                    f[i|j|k]=(x-y+mod)%mod;
                }
        if(type==-1)
        {
            f[0]=1ll*f[0]*invlim[lim]%mod;
            for(int i=1;i<=(lim>>1);i++)
            {
                f[i]=1ll*f[i]*invlim[lim]%mod;
                if(i!=(lim>>1))
                {
                    f[lim-i]=1ll*f[lim-i]*invlim[lim]%mod;
                    swap(f[i],f[lim-i]);
                }
            }
        }
    }
}
namespace sieve
{
    int f[300005],p[300005];
    bool np[300005];
    void Euler(int n)
    {
        int cnt=0;
        np[1]=f[1]=1;
        for(int i=2;i<=n;i++)
        {
            if(!np[i])
            {
                p[++cnt]=i;
                f[i]=1;
            }
            for(int j=1;j<=cnt&&i*p[j]<=n;j++)
            {
                np[i*p[j]]=1;
                if(i%p[j]==0)
                {
                    f[i*p[j]]=f[i/p[j]]*p[j];
                    break;
                }
                f[i*p[j]]=f[i]*f[p[j]];
            }
        }
        for(int i=1;i<=n;i++)
            f[i]--;
    }
}
using namespace ntt;
using namespace sieve;
int tmp[524289],tmpb[524289],rev[524289];
int lenans=0;
namespace cdqfft
{
    void Multiply(int tmp[],int tmpb[],int rev[],int lim)
    {
        if(lim<=32)
        {
            int res[33]={0};
            for(int i=0;i<=lim&&tmp[i];i++)
                for(int j=0;j<=lim&&tmpb[j];j++)
                    res[i+j]=(res[i+j]+1ll*tmp[i]*tmpb[j]%mod)%mod;
            memcpy(tmp,res,sizeof(int)*33);
            return;
        }
        initNTT(lim);
        NTT(tmp,rev,lim,1);
        NTT(tmpb,rev,lim,1);
        for(int i=0;i<=lim;i++)
            tmp[i]=1ll*tmp[i]*tmpb[i]%mod;
        NTT(tmp,rev,lim,-1);
    }
    void cdqFFT(int l,int r,int lim,int L)
    {
        if(l==r)
        {
            tmp[0]=l-f[l]-1;
            tmp[1]=f[l];
            if(f[l])
                lenans++;
            return;
        }
        int mid=l+r>>1;
        memset(tmp,0,sizeof(int)*(lim+1));
        const int N=lim+1;
        int *tmpc=new int[N];
        memcpy(tmpc,tmpb,sizeof(int)*(lim+1));
        cdqFFT(l,mid,lim>>1,L-1);
        memcpy(tmpb,tmp,sizeof(int)*(lim+1));
        memset(tmp,0,sizeof(int)*(lim+1));
        cdqFFT(mid+1,r,lim>>1,L-1);
        for(int i=0;i<=lim;i++)
            rev[i]=(rev[i>>1]>>1)|((i&1)<<L);
        Multiply(tmp,tmpb,rev,lim);
        memcpy(tmpb,tmpc,sizeof(int)*(lim+1));
        delete tmpc;
    }
}
int n;
using namespace cdqfft;
signed main()
{
//  __BEGIN_MULTITEST__
#ifndef ONLINE_JUDGE
    freopen("P12321.in","r",stdin);
    freopen("P12321.out","w",stdout);
#endif
    read(n);
    if(n==1)
        return 0*printf("1\n");
    Euler(n);
    int lim=1,L=-1,len=n;
    while(lim<len)
    {
        lim<<=1;
        L++;
    }
    initinv(lim);
    cdqFFT(2,n,lim,L);
    for(int i=0;i<n;i++)
        write(tmp[i],'\n');
//  __END_MULTITEST__
    return 0;
}