列表

详情

NC17695. Rikka with Equation

描述

Today, Yuta gives Rikka a simple math task: given a positive integer array A of length n and a positive integer m, does the equation have any solutions?

Rikka solves this problem easily: is always a solution of this equation.

And then, Yuta shows a much harder version of this task:

For a positive integer array A of length n and a positive integer m, let f(A,m) be the number of different integer vectors x which satisfy xi ∈ [0,m) and .

For example, when A=[1,1], m=2, there are 2 integer vectors [0,0],[1,1] satisfy the previous conditions. So f([1,1],2) is equal to 2.

Now Yuta shows a positive integer array B of length n and a positive integer M. B has N=2n-1 non-empty subsequences A1,...,AN. For each integer m ∈ [1,M], Yuta wants to know .

For example, when B=[1,1] and M = 3, Rikka needs to calculate f([1],1) x 2 + f([1,1],1), f([1],2) x 2 + f([1,1],2) and f([1],3) x 2 + f([1,1],3).

This task is too hard for Rikka. So she wants you to help her.

输入描述

The first line contains a single integer t(1 ≤ t ≤ 3), the numebr of the testcases.

For each testcase, the first line contains two integers n,M(1 ≤ n,M ≤ 105). The second line contains n positive integers Bi(1 ≤ Bi ≤ 105).

输出描述

For each testcase, let wm be equal to . You only need to output a single line with a single integer, , i.e., the exclusive OR sum of all wi.

示例1

输入: 

2
5 5
1 2 3 4 5
10 10
1 2 3 4 5 6 7 8 9 10

输出: 

1079
933958261

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 400ms, 内存消耗: 14936K, 提交时间: 2018-08-19 12:35:36 

#include<bits/stdc++.h>
#define maxn 101010

using namespace std;
typedef long long ll;
const ll M=998244353;
ll cnt[maxn],a[maxn],b[maxn],w[maxn],ans,inv[maxn],f[maxn],n,m;
vector <int> h[maxn];
ll pow_(ll x,ll y){
    ll rt=1;
    while (y){
        if (y&1) rt=rt*x%M;
        x=x*x%M; y>>=1;
    }
    return rt;
}

int main(){
    for (int i=1;i<maxn;i++) for (int j=1;j*i<maxn;j++) h[i*j].push_back(i);
    for (int i=1;i<maxn;i++) inv[i]=pow_(i,M-2),f[i]=i;
    for (int i=1;i<maxn;i++) for (int j=2;j*i<maxn;j++) (f[i*j]+=(M-f[i]))%=M;
    int T; cin >> T;
    while (T--){
        cin >> n >> m;
        for (int i=1;i<maxn;i++) cnt[i]=0;
        for (int i=0;i<n;i++){
            scanf("%d",&b[i]);
            for (int j=0;j<h[b[i]].size();j++){
                int u=h[b[i]][j];
                cnt[u]++;
            }
        }
        for (int i=1;i<=m;i++) {
            w[i]=0;
            for (int j=0;j<h[i].size();j++){
                int u=h[i][j];
                if (cnt[u]) (w[i]+=(pow_(i+1,cnt[u])-1)*f[u])%=M;
            }
            w[i]=w[i]*inv[i]%M;
        }
        ans=0; for (int i=1;i<=m;i++) ans^=w[i];
        cout << ans << endl;
    }
    return 0;
}

C++ 解法, 执行用时: 150ms, 内存消耗: 1896K, 提交时间: 2021-05-26 13:22:19 

#include<cstdio>
using namespace std;
const int mod = 998244353, N = 1e5;
int qp(int a, int x){
	int i = 1;
	for(;x;x >>= 1, a = 1ll * a * a % mod)if(x & 1)i = 1ll * i * a % mod;
	return i;
}
int p[N + 1], phi[N + 1], v[N + 1], inv[N + 1];
int main(){
	int T, n, m, i, j, k;
	for(phi[1] = inv[1] = 1, i = 2;i <= N;i++){
		if(!v[i])phi[p[++p[0]] = i] = i - 1;
		for(j = 1;j <= p[0] && i * p[j] <= N;j++){
			v[i * p[j]] = 1;
			if(i % p[j])phi[i * p[j]] = phi[i] * (p[j] - 1);
			else{
				phi[i * p[j]] = phi[i] * p[j];
				break;
			}
		}inv[i] = mod - 1ll * mod / i * inv[mod % i] % mod;
	}scanf("%d", &T);
	while(T--){
		scanf("%d%d", &n, &m);
		for(i = 0;i <= N;i++)v[i] = 0;
		for(i = 1;i <= n;i++){
			scanf("%d", &j);
			v[j]++;
		}for(i = 1;i <= m;i++)p[i] = 0;
		for(i = 1;i <= m;i++){
			for(j = i, k = 0;j <= N;j += i)k += v[j];
			for(j = i;j <= m;j += i)p[j] = (p[j] + 1ll * phi[i] * qp(j + 1, k) % mod) % mod;
		}for(i = 1, j = 0;i <= m;i++){
			p[i] = (1ll * p[i] * inv[i] % mod - 1 + mod) % mod;
			j ^= p[i];
		}printf("%d\n", j);
	}return 0;
}

上一题

© 2025 nowcoder.com