Submission #508539

#	Time	Username	Problem	Language	Result	Execution time	Memory
508539		KoD	Set (COCI21_set)	C++17	110 / 110	399 ms	20876 KiB

Main

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

template <int mod> struct Fp {
    int x;
    Fp(int x = 0) : x(x) {}
    
    Fp& operator+=(const Fp& other) {
        if ((x += other.x) >= mod) x -= mod;
        return *this;
    }
    Fp& operator-=(const Fp& other) {
        if ((x -= other.x) < 0) x += mod;
        return *this;
    }
    Fp& operator*=(const Fp& other) {
        x = (long long)x * other.x % mod;
        return *this;
    }
    Fp& operator/=(const Fp& other) {
        return *this *= other.inv();
    }

    Fp operator+(const Fp& other) const {
        return Fp(*this) += other;
    }
    Fp operator-(const Fp& other) const {
        return Fp(*this) -= other;
    }
    Fp operator*(const Fp& other) const {
        return Fp(*this) *= other;
    }
    Fp operator/(const Fp& other) const {
        return Fp(*this) /= other;
    }

    Fp pow(int exp) const {
        Fp ret(1), mul(*this);
        while (exp > 0) {
            if (exp & 1) ret *= mul;
            mul *= mul;
            exp >>= 1;
        }
        return ret;
    }
    Fp inv() const {
        return pow(mod - 2);
    }
};

template <int m> void transform(vector<Fp<m>>& f, const Fp<m> omega) {
    const int n = f.size();
    for (int i = 1; i < n; i *= 3) {
        for (int j = 0; j < n; ++j) {
            if ((j / i) % 3 == 0) {
                const auto a = f[j], b = f[j + i], c = f[j + i * 2];
                f[j] = a + b + c;
                f[j + i] = a + b * omega + c * omega * omega;
                f[j + i * 2] = a + b * omega * omega + c * omega;
            }
        }
    }
}

template <int m, int r> vector<int> square(const vector<int>& a) {
    const int n = a.size();
    vector<Fp<m>> f(n);
    for (int i = 0; i < n; ++i) {
        f[i] = a[i];
    }
    const auto omega = Fp<m>(r).pow((m - 1) / 3);
    transform<m>(f, omega);
    for (int i = 0; i < n; ++i) {
        f[i] *= f[i];
    }
    transform<m>(f, omega * omega);
    const auto inv = Fp<m>(n).inv();
    vector<int> b(n);
    for (int i = 0; i < n; ++i) {
        b[i] = (f[i] * inv).x;
    }
    return b;
}

constexpr int mod1 = 99999931;
constexpr int root1 = 2;

constexpr int mod2 = 99999043;
constexpr int root2 = 2;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, K;
    std::cin >> N >> K;
    vector<int> pow(K + 1);
    pow[0] = 1;
    for (int i = 0; i < K; ++i) {
        pow[i + 1] = pow[i] * 3;
    }
    const int L = pow[K];
    vector<int> inv(N);
    vector<int> freq(L);
    for (int i = 0; i < N; ++i) {
        int x = 0;
        for (int j = 0; j < K; ++j) {
            char c;
            std::cin >> c;
            x += (c - '1') * pow[j];
            inv[i] += (('4' - c) % 3) * pow[j];
        }
        freq[x] += 1;
    }
    const auto a = square<mod1, root1>(freq);
    const auto b = square<mod2, root2>(freq);
    vector<long long> c(L);
    for (int i = 0; i < L; ++i) {
        // x = a[i] mod M1
        // x = b[i] mod M2
        const int k = ((Fp<mod2>(b[i]) - Fp<mod2>(a[i])) / Fp<mod2>(mod1)).x;
        c[i] = (long long)mod1 * k + a[i];
    }
    long long ans = 0;
    for (int i = 0; i < N; ++i) {
        ans += c[inv[i]];
    }
    std::cout << (ans - N) / 6 << '\n';
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 70 / 70