LGP7580题解

设：

\[g(x)=\prod_{i=1}^{k_i}\binom {m} {c_{d,i}+m}
\]

那么很明显有：

\[f= a * g
\]

再看一眼 \(g\)，我们发现 \(g\) 是积性函数。

使用P5495的办法即可做到 \(O(m+n\log \log n)\)，轻松通过此题。

#include<cstdio>

const int M=1e7+5,mod=998244353;

typedef unsigned uint;

int n,m,top,f[24],g[M],pri[M],C[M];uint ans,b[M],a[M];

int fac[M],ifac[M];bool zhi[M];

uint seed;

inline int Add(const int&a,const int&b){

    return a+b>=mod?a+b-mod:a+b;

}

inline uint randomdigit(){

    seed^=seed<<13;

    seed^=seed>>17;

    seed^=seed<<5;

    return seed;

}

signed main(){

    register int i,j,x;

    scanf("%d%d%u",&n,&m,&seed);

    a[1]=randomdigit()%mod;

    fac[0]=ifac[0]=fac[1]=ifac[1]=1;

	fac[2]=2;ifac[2]=499122177;

	for(i=3;i<=m+24;++i){

		fac[i]=1ll*fac[i-1]*i%mod;

		ifac[i]=1ll*(mod-mod/i)*ifac[mod%i]%mod;

	}

	for(i=1;i<=m+24;++i)ifac[i]=1ll*ifac[i]*ifac[i-1]%mod;

    for(i=0;i<24;++i){

        f[i]=1ll*ifac[i]*ifac[m]%mod*fac[i+m]%mod;

    }

    for(i=2;i<=n;++i){

        a[i]=randomdigit()%mod;

        if(!zhi[i])pri[++top]=i;

        for(j=1;j<=top&&(x=i*pri[j])<=n;++j){

            zhi[x]=1;if(!(i%pri[j]))break;

        }

    }

    for(i=1;i<=top;++i){

        for(j=n/pri[i];j;--j){

        	for(long long x,k=pri[i],cnt=1;(x=j*k)<=n;++cnt,k*=pri[i]){

                a[x]=Add(a[x],1ll*a[j]*f[cnt]%mod);

            }

        }

    }

    for(i=1;i<=n;++i)ans^=a[i];

    printf("%u",ans);

}

巴特西

LGP7580题解

最新文章

热门文章