QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#736332 | #9619. 乘积,欧拉函数,求和 | caojc | WA | 968ms | 5832kb | C++20 | 3.2kb | 2024-11-12 10:09:26 | 2024-11-12 10:09:26 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define lll __int128
#define db(args...){\
string _s = #args; replace(_s.begin(), _s.end(), ',', ' ');\
stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); cout << '\n';}
void err(istream_iterator<string> it){}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
cout << *it << " = " << a << ' ';
err(++it, args...);
}
// 9.39
const int mod = 998244353;
void add(ll &x, ll y) {
x += y;
if (x >= mod) x -= mod;
}
ll ksm(ll a, ll b = mod - 2) {
ll res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod, b /= 2;
}
return res;
}
const int N = 3001;
int pri[N], visi[N], tot, id[N];
ll v[N];
void init() {
for (int i = 2; i < N; i++) {
if (!visi[i]) {
visi[i] = i;
pri[++tot] = i;
}
for (int j = 1; j <= tot; j++) {
if (pri[j] * i >= N) break;
visi[i * pri[j]] = pri[j];
if (i % pri[j] == 0) break;
}
v[i] = (i - 1) * ksm(i) % mod;
}
memset(id, -1, sizeof id);
}
void solve() {
init();
int n;
cin >> n;
int B = 1;
while ((B + 1) * (B + 1) <= 3000) B++;
int cp;
for (int i = 1; i <= tot && pri[i] <= B; i++) {
cp = i;
id[pri[i]] = i - 1;
}
map<int, vector<int>> mp;
vector<int> st(n), a(n);
for (int i = 0; i < n; i++) {
int x;
cin >> x;
a[i] = x;
int big = 0;
while (x > 1) {
int p = visi[x];
if (id[p] != -1) st[i] |= 1 << id[p];
else big = p;
while (x % p == 0) x /= p;
}
mp[big].push_back(i);
}
#define a2 array<ll, 2>
vector<a2> f(1 << cp, {0, 0});
f[0][0] = 1;
vector<ll> val(1 << cp, 1);
for (int i = 0; i < 1 << cp; i++) {
for (int j = 0; j < cp; j++) {
if (i >> j & 1)
val[i] = val[i] * v[pri[j + 1]] % mod;
}
}
for (auto [big, pos] : mp) {
for (auto i : pos) {
vector<a2> nf = f;
for (int x = 0; x < 1 << cp; x++) {
for (int t = 0; t < 2; t++) {
int nx = x | st[i];
add(nf[nx][big != 0], f[x][t] * a[i] % mod * val[nx ^ x] % mod * (big && t == 0 ? v[big] : 1) % mod);
}
}
f = move(nf);
// for (int x = 0; x < 1 << cp; x++) {
// for (int t = 0; t < 2; t++) {
// if (f[x][t]) {
// db(x, t, f[x][t]);
// }
// }
// }
}
for (int x = 0; x < 1 << cp; x++) add(f[x][0], f[x][1]);
}
ll res = 0;
for (int x = 0; x < 1 << cp; x++) res += f[x][0];
res %= mod;
cout << res << '\n';
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
/*
g++ 1.cpp -std=c++20 -o 1 && ./1 < in.txt > out.txt
*/
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 5700kb
input:
5 1 6 8 6 2
output:
892
result:
ok single line: '892'
Test #2:
score: 0
Accepted
time: 0ms
memory: 5672kb
input:
5 3 8 3 7 8
output:
3157
result:
ok single line: '3157'
Test #3:
score: -100
Wrong Answer
time: 968ms
memory: 5832kb
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:
176655588
result:
wrong answer 1st lines differ - expected: '50965652', found: '176655588'