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

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 2021牛客暑期多校训练营4 H-Convolution -> 正文阅读

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

传送门

题目大意

题解

由题意得

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

?所以

$b_i= \sum\limits_{1≤j,k≤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\limits_{1≤x,y≤n,xy=i,gcd(x,y)=1} \sum\limits_{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;
}