提出 #49984361

---

ソースコード 拡げる

#include <bits/stdc++.h>
#include <atcoder/modint>

namespace {
    using ModInt [[maybe_unused]] = atcoder::modint998244353;
    using Num [[maybe_unused]] = uint64_t;
    using Vec [[maybe_unused]] = std::vector<Num>;
    using Set [[maybe_unused]] = std::set<Num>;
    using Mset [[maybe_unused]] = std::multiset<Num>;
    using Edges [[maybe_unused]] = std::vector<std::vector<Num>>;

    template<typename T>
    using Q [[maybe_unused]] = std::queue<T>;

    template<typename T>
    using PQ [[maybe_unused]] = std::priority_queue<T, std::vector<T>, std::greater<T>>;
}

std::vector<Num> primes;

void init_primes(void) {
    Num power2 = 1;
    power2 <<= 29;

    std::vector<Num> diffs {3, 33};
    for(const auto& d : diffs) {
        primes.push_back(power2 - d);
    }
}

struct BigNum {
    std::vector<Num> rems;

    BigNum(const std::string& s) {
        rems.resize(primes.size());

        for(size_t i{0}; i<primes.size(); ++i) {
            const auto& p = primes.at(i);
            for(const auto& c : s) {
                const Num d = c - '0';
                rems.at(i) = (rems.at(i) * 10 + d) % p;
            }
        }
    }
};

void solve(std::istream& is, std::ostream& os) {
    init_primes();
    size_t n_primes = primes.size();
    size_t n {0};
    is >> n;

    std::vector<BigNum> ns;
    std::vector<std::unordered_map<Num, size_t>> rems(n_primes);
    for(size_t i{0}; i<n; ++i) {
        std::string s;
        is >> s;
        ns.emplace_back(s);
        for(size_t ip{0}; ip<n_primes; ++ip) {
            rems[ip][ns.back().rems[ip]] += 1;
        }
    }

    size_t total {0};
    for(size_t i{0}; i<n; ++i) {
        for(size_t j{i}; j<n; ++j) {
            size_t ct {n};
            for(size_t ip{0}; ip<n_primes; ++ip) {
                const auto r = (ns[i].rems[ip] * ns[j].rems[ip]) % primes[ip];
                const auto& rs = rems[ip];
                auto it = rs.find(r);
                if (it == rs.end()) {
                    ct = 0;
                    break;
                }
                ct = std::min(ct, it->second);
            }
            total += ct * (1 + (i != j));
        }
    }

    os << total << "\n";
}

int main(void) {
    solve(std::cin, std::cout);
    return 0;
}

提出情報

ジャッジ結果