代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

#define P 998244353

using namespace std;

typedef long long ll;

int n, m, op;

vector <int> D[400010];

ll A[400010], B[400010], SB[400010], mu[400010], Smu[400010], lans = 0, ans = 0;

ll SV[400010], O[400010];

ll calc(ll x) {
    return x * (x + 1) / 2 % P;
}

int main() {
    //freopen("lalaland.in", "r", stdin);
    //freopen("lalaland.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &op);
    /*for(int i = 1; i <= 400000; i++)
        for(int j = i; j <= 400000; j += i) O[j]++;
    for(int i = 1; i <= 400000; i++) D[i].resize(O[i]);
    for(int i = 1; i <= 400000; i++)
        for(int j = i; j <= 400000; j += i) D[j][--O[j]] = i;*/
    for(int i = 1; i <= 400000; i++)
        for(int j = i; j <= 400000; j += i) D[j].push_back(i);
    mu[1] = 1;
    for(int i = 1; i <= 400000; i++)
        for(int j = i + i; j <= 400000; j += i) mu[j] -= mu[i];
    for(int i = 1; i <= 400000; i++) {
        ll ans = 0;
        for(int j = 0; j < D[i].size(); j++) {
            int t = D[i][j];
            ans = (ans + mu[t] * calc(i / t) % P * t) % P;
        }
        A[i] = (A[i - 1] + i * ans * 2ll % P - (i == 1)) % P;
    }
    for(int i = 1; i <= 400000; i++) {
        ll ans = 0;
        for(int j = 0; j < D[i].size(); j++) {
            int t = D[i][j];
            Smu[t] += mu[i];
            ans = (ans + mu[t] * Smu[t] % P) % P;
        }
        B[i] = (B[i - 1] + mu[i] * ans * 2 - (i == 1)) % P;
    }
    for(int i = 1; i <= 400000; i++)
        for(int j = i; j <= 400000; j += i)
            SB[j] = (SB[j] + B[i] * mu[j / i]) % P;
    for(int i = 1; i <= 400000; i++) SV[i] = 1;
    //for(int i = 1; i <= 400000; i++) ans = (ans + SV[i] * SB[i]) % P;
    for(int i = 1; i <= n; i++) {
        ll a;
        scanf("%lld", &a);
        if(op == 1) a = ((19891989ll * lans) + a) % m + 1;
        ll av = A[a];
        for(int j = 0; j < D[a].size(); j++) {
            int t = D[a][j];
            ll det = av * SV[t] % P;
            ans = (ans + det * SB[t]) % P;
            SV[t] = (SV[t] + det) % P;
        }
        if(op || i == n) printf("%lld\n", lans = (ans % P + P) % P); //!!!
    }
    return 0;
}

评测结果