牛客多校第四场 H.Convolution 数论 推式子

牛客多校第四场 H.Convolution 数论 推式子

题意

定义运算

[a igotimes b = sum_{i}p_i^{|e_{a_i} - e_{b_i}|} ]

(e_{x_i})表示(x)的第(i)个质因子的指数

给定(a_1...a_n)

求

[b_i = sum_{i leq k,j leq n,j igotimes k =i} a_jk^c ]

分析

现进行一些转化

有常用的等式

[|a-b|= max(a,b) - min(a,b) ]

那么

[aigotimes b = sum_{i}p_i^{max(e_{a_i},e_{b_{i}}) - min(e_{a_i},e_{b_i})} ]

显然这就是(frac{[a,b]}{(a,b)} = frac{ab}{(a,b)^2})

那么

[b_i = sum_{j=1}^nsum_{k=1}^n[frac{jk}{(j,k)^2} = i]a_j k^c\ ]

考虑对称性构造(x' = frac{j}{(j,k)},y' = frac{k}{(j,k)})

那么常用套路，枚举(gcd = d),(j = dx',k = dy')

[b_i = sum_{x' | i} sum_{d=1}^{min(lfloorfrac{i}{x'} floor,lfloorfrac{i}{y'} floor)}a_{dx'}(dy')^c ]

发现每次计算(b_i)中后式会多次重复计算

考虑计算

[f_{x',m} = sum_{d=1}^m a_{dx'}d^c ]

显然这可以(O(1))递推，这样式子就只依赖(a) 计算贡献时可以额外乘上(y)的贡献

[b_i = sum_{x|i} f_{x',u} y'^c ]

代码

const int MOD = 998244353;

inline int mul(int a,int b){
	int res = (ll)a * b % MOD;
	if(res < 0) res += MOD;
	return res;
}

inline void add(int &a,int b){
	a += b;
	if(a >= MOD) a -= MOD;
}

inline void sub(int &a,int b){
	a -= b;
	if(a < 0) a += MOD;
}

const int maxn = 1e6 + 5;

int ksm(int a,int b = MOD - 2,int m = MOD){
	int ans = 1;
	int base = a;
	while(b){
		if(b & 1) ans = (ll)ans * base % m;
		base = (ll)base * ans % m;
		b >>= 1;
	}
	return ans;
}


int p[maxn];

int main(){
	int n = rd();
	int c = rd();
	for(int i = 1;i <= n;i++)
		p[i] = ksm(i,c);
	vector<int> v(n + 1);
	vector<int> ans(n + 1);
	for(int i = 1;i <= n;i++){
		v[i] = rd();
	}
	int res = 0;
	for(int i = 1;i <= n;i++){
		vector<int> f(n / i + 1);
		for(int j = 1;j * i <= n;j++)
			f[j] = f[j - 1],add(f[j],mul(v[i * j],p[j]));
		for(int j =1;i * j <= n;j++)
			if(__gcd(i,j) == 1){
				int u = n / max(i,j);
				add(ans[i * j],mul(f[u],p[j]));		
			}
	}
	for(int i = 1;i <= n;i++)
		res ^= ans[i];
	printf("%d",res);
}