Submission #533958

#	Time	Username	Problem	Language	Result	Execution time	Memory
533958		AaronJ	Set (COCI21_set)	C++98	110 / 110	384 ms	21700 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