求助TLE30分

VinstaG173 @ 2021-03-30 18:20:06

by VinstaG173 @ 2021-03-30 18:20:19

#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
#define rg register
#define ll long long
const int ntf=998244353;
const int maxl=530007;
int n,m,v,L=1;
int rev[maxl],tms[maxl];
ll f[maxl],g[2][maxl],h[maxl],s[maxl],t[maxl],A[maxl],B[maxl],Inv[maxl];
inline ll read()
{
    ll x=0;char c=getchar();
    while(c<'0'||c>'9')
    {
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0',c=getchar();
    }
    return x;
}
void exgcd(ll a,ll b,ll &d,ll &x,ll &y)
{
    (b)?(exgcd(b,a%b,d,y,x),y-=x*(a/b)):(x=1,y=0,d=a);
}
inline ll _inv(ll a)
{
    ll d,x,y;
    exgcd(a,ntf,d,x,y);
    return (d==1)?(x+ntf)%ntf:-1;
}
inline void setrev(ll lim,ll l)
{
    for(rg int i=0;i<lim;++i)
    {
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
    }
}
inline ll qpw(rg ll x,rg ll k)
{
    rg ll r=1;
    while(k)
    {
        (k&1)&&(r=r*x%ntf),x=x*x%ntf,k>>=1;
    }
    return r;
}
inline void NTT(ll *a,int opt,int lim)
{
    for(rg int i=0;i<lim;++i)
    {
        if(i<rev[i])
        {
            a[i]^=a[rev[i]]^=a[i]^=a[rev[i]];
        }
    }
    for(rg int m=1;m<lim;m<<=1)
    {
        ll tmp=qpw(3,(ntf-1)/(m<<1)*opt+ntf-1);
        for(rg int s=0;s<lim;s+=m<<1)
        {
            ll u=1;
            for(rg int t=0;t<m;++t,u=u*tmp%ntf)
            {
                ll a1=a[s+t],a2=a[s+t+m]*u%ntf;
                a[s+t]=(a1+a2)%ntf,a[s+t+m]=(a1-a2+ntf)%ntf;
            }
        }
    }
    if(~opt)return;
    int inv=_inv(lim);
    for(rg int i=0;i<lim;++i)a[i]=a[i]*inv%ntf;
}
inline void mul(ll *a,ll *b,int lim)
{
    memset(A,0,sizeof(A)),memset(B,0,sizeof(B));
    for(rg int i=0;i<(lim>>1);++i)A[i]=a[i],B[i]=b[i];
    NTT(A,1,lim);
    NTT(B,1,lim);
    for(rg int i=0;i<lim;++i)
    {
        A[i]=A[i]*B[i]%ntf;
    }
    NTT(A,-1,lim);
    for(rg int i=0;i<lim;++i)a[i]=A[i];
}
inline void _inv(ll *a,int Lim)
{
    memset(g,0,sizeof(g));
    int lev=0,lid=1,lim=2,l=1;
    g[lev][0]=_inv(a[0]);
    while(lid<=Lim)
    {
        lev^=1,setrev(lim,l);
        for(rg int i=0;i<lid;++i)g[lev][i]=(g[lev^1][i]<<1)%ntf;
        mul(g[lev^1],g[lev^1],lim),mul(g[lev^1],a,lim);
        for(rg int i=0;i<lid;++i)g[lev][i]=(g[lev][i]-g[lev^1][i]+ntf)%ntf,g[lev^1][i]=0;
        lim<<=1,lid<<=1,++l;
    }
    for(int i=0;i<L;++i)a[i]=g[lev][i];
}
inline void diff(ll *a,ll *r,int lim)
{
    for(rg int i=1;i<lim;++i)r[i-1]=a[i]*i%ntf;
    r[lim]=0;
}
inline void inte(ll *a,ll *r,int lim)
{
    for(rg int i=1;i<lim;++i)r[i]=a[i-1]*_inv(i)%ntf;
    r[0]=0;
}
inline void ln(ll *a,int lim)
{
    memset(h,0,sizeof(h));
    int l=0;
    while(1<<l<lim)++l;
    diff(a,h,lim);
    _inv(a,lim);
    setrev(lim,l);
    mul(h,a,lim);
    inte(h,a,lim);
}
inline void _exp(ll *a,int Lim)
{
    memset(s,0,sizeof(s));
    memset(t,0,sizeof(t));
    int lid=1,lim=2,l=1;
    s[0]=1;
    while(lid<=Lim)
    {
        for(rg int i=0;i<lid;++i)t[i]=s[i];
        ln(t,lid);
        for(rg int i=0;i<lid;++i)t[i]=((!i)+a[i]-t[i]+ntf)%ntf;
        setrev(lim,l),mul(s,t,lim);
        lim<<=1,lid<<=1,++l;
    }
    for(int i=0;i<Lim;++i)a[i]=s[i];
}
int main()
{
    scanf(" %d %d",&n,&m);
    while(L<=(m<<1))L<<=1;
    Inv[1]=1;
    for(rg int i=2;i<=m;++i)Inv[i]=(ntf-ntf/i)*Inv[ntf%i]%ntf;
    while(n--)scanf(" %d",&v),++tms[v];
    for(rg int i=1;i<=m;++i)
    {
        if(!tms[i])continue;
        for(rg int j=1,k=i;k<L;++j,k+=i)
        {
            f[k]=(f[k]+(ntf-Inv[j])*tms[i]%ntf)%ntf;
        }
    }
    _exp(f,L);
    _inv(f,L);
    for(int i=1;i<=m;++i)printf("%lld\n",f[i]);
    return 0;
}

by VinstaG173 @ 2021-03-30 18:28:41

不 inv 再换掉 memset 卡过去了 /ll

咍 此帖终

by hsfzLZH1 @ 2021-03-30 20:26:24

现在换我卡不过去了。。