QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#776041#9619. 乘积,欧拉函数,求和Bicycle_23WA 1585ms4672kbC++232.7kb2024-11-23 17:23:452024-11-23 17:23:46

Judging History

你现在查看的是最新测评结果

  • [2024-11-23 17:23:46]
  • 评测
  • 测评结果:WA
  • 用时:1585ms
  • 内存:4672kb
  • [2024-11-23 17:23:45]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

constexpr int maxn = 2e5 + 5;
constexpr int mod = 998244353;
constexpr int r = 1ll << 16;
constexpr int prime[16] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};

int lowbit(int x) {return x & (-x);}

int qpow(int x, int y)
{
	int res = 1;
	while (y)
	{
		if (y & 1) res = res * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}

void fwt_or(vector<int> &a, bool flag)
{
	int len = (int)a.size();
	for (int i = 2; i <= len; i <<= 1)
		for (int j = 0; j < len; j += i)
			for (int k = 0; k < i / 2; k++)
				if (flag)
				{
					int x = a[j + k], y = (a[j + k] + a[j + k + i / 2]) % mod;
					a[j + k] = x;
					a[j + k + i / 2] = y;
				}
				else
				{
					int x = a[j + k], y = ((mod - a[j + k]) % mod + a[j + k + i / 2]) % mod;
					a[j + k] = x;
					a[j + k + i / 2] = y;
				}
}

void mul_or(vector<int> &a, vector<int> &b)
{
	int len = 1ll << 16;
	// while (len < max((int)a.size(), (int)b.size())) len <<= 1;
	a.resize(len); b.resize(len);
	fwt_or(a, 1); fwt_or(b, 1);
	for (int i = 0; i < len; i++) a[i] = a[i] * b[i] % mod;
	fwt_or(a, 0);
}

void solve()
{
	int n; cin >> n;
	vector<int> a(n + 1, 0);
	vector<array<int, 3> > p(n + 1);
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		int x = a[i];
		p[i][2] = x;
		for (int j = 0; j < 16; j++)
		{
			if (x % prime[j] == 0)
			{
				while (x % prime[j] == 0) x /= prime[j];
				p[i][1] |= (1ll << j);
			}
		}
		p[i][0] = x;
	}

	sort(p.begin() + 1, p.end());
	vector<int> ans(1ll << 16, 0);
	ans[0] = 1;

	for (int i = 1, j = 1; i <= n; i = j)
	{
		while (j <= n && p[i][0] == p[j][0]) ++j;
		vector<int> tmp(1ll << 16, 0);
		tmp[0] = 1;
		for (int k = i; k < j; k++)
		{
			vector<int> tmpx(1ll << 16, 0);
			for (int l = 0; l < r; l++)
			{
				int t = l | p[k][1];
				tmpx[t] = (tmpx[t] + tmp[l] * p[k][2] % mod) % mod;
			}
			for (int l = 0; l < r; l++) tmp[l] = (tmp[l] + tmpx[l]) % mod;
		}
		if (p[i][0] != 1)
		{
			int invp = qpow(p[i][0], mod - 2);
			for (int l = 1; l < r; l++) tmp[l] = tmp[l] * invp % mod * (p[i][0] - 1) % mod;
			tmp[0] = (tmp[0] + (tmp[0] - 1) * invp % mod * (p[i][0] - 1) % mod) % mod;
			tmp[0] = (tmp[0] + 1) % mod;
		}
		mul_or(ans, tmp);
	}

	int res = 0;
	for (int l = 0; l < r; l++)
	{
		int x = l, tmp = ans[l];
		while (x)
		{
			int pri = prime[(int)log2(lowbit(x))];
			x -= lowbit(x);
			int invp = qpow(pri, mod - 2);
			tmp = (tmp * invp % mod * (pri - 1)) % mod;
		}
		res = (res + tmp) % mod;
	}
	cout << res;
}

signed main()
{
	cin.tie(0); cout.tie(0);
	ios::sync_with_stdio(0);
	int _ = 1;
	// cin >> _;
	while (_--) solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 75ms
memory: 4564kb

input:

5
1 6 8 6 2

output:

892

result:

ok single line: '892'

Test #2:

score: 0
Accepted
time: 75ms
memory: 4672kb

input:

5
3 8 3 7 8

output:

3157

result:

ok single line: '3157'

Test #3:

score: -100
Wrong Answer
time: 1585ms
memory: 4672kb

input:

2000
79 1 1 1 1 1 1 2803 1 1 1 1 1 1 1609 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2137 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 613 1 499 1 211 1 2927 1 1 1327 1 1 1123 1 907 1 2543 1 1 1 311 2683 1 1 1 1 2963 1 1 1 641 761 1 1 1 1 1 1 1 1 1 1 1 1489 2857 1 1 1 1 1 1 1 1 1 1 1 1 1 967 1 821 1 1 1 1 2143 1861...

output:

705575283

result:

wrong answer 1st lines differ - expected: '50965652', found: '705575283'