QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#736332#9619. 乘积,欧拉函数,求和caojcWA 968ms5832kbC++203.2kb2024-11-12 10:09:262024-11-12 10:09:26

Judging History

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

  • [2024-11-12 10:09:26]
  • 评测
  • 测评结果:WA
  • 用时:968ms
  • 内存:5832kb
  • [2024-11-12 10:09:26]
  • 提交

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'