[数据结构与算法]2021牛客暑期多校训练营4 H-Convolution

传送门

题目大意

题解

由题意得

$x?y=\frac{2xy}{gcd(x,y{)}^2}$

?所以

$b_i=\sum _{1\le j,k\le n,\frac{jk}{gcd(j,k{)}^2}=i}{a}_j{k}^c$

设 $g=gcd(j,k),x=\frac{j}{g},y=\frac{k}{g}$
化简可得

$b_i=y^c\sum _{1\le x,y\le n,xy=i,gcd(x,y)=1}\sum _{g=1}^{min(\frac{n}{x},\frac{n}{x})}{a}_{xg}{g}^c$

code

#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
long long ksm(long long x,long long y){
    long long res=1;
    while(y)
	{
        if(y&1) res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}
int n,c;
int a[1000010];
long long powc[1000010],sum[1000010],b[1000010];
int main()
{
    int i,j;
    scanf("%d%d",&n,&c);
    for(i=1;i<=n;i++)
	{
        scanf("%d",&a[i]);
        powc[i]=ksm(i,c);
    }
    for(i=1;i<=n;i++)
	{
        int mx=n/i;
        for(j=1;j<=mx;j++)
        sum[j]=(sum[j-1]+a[i*j]*powc[j])%mod;
        
        for(j=1;j<=mx;j++)
		{
            if(__gcd(i,j)>1) continue;
            b[i*j]=(b[i*j]+powc[j]*sum[min(mx,n/j)])%mod;
        }
    }
    for(i=1;i<=n;i++)
    b[i]^=b[i-1];
    printf("%lld\n",b[n]);
    return 0;
}