제출 #1288959

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288959		Gev2706	PIN (CEOI10_pin)	C++20	100 / 100	42 ms	13912 KiB

pin

// PIN pairs by exact Hamming distance D (n <= 5e4, len=4, D in [0..4])
// Counts, for each k=0..4, A_k = sum over subsets S (|S|=k) of pairs that agree on all positions in S.
// Then invert: if x_t = #pairs that agree on exactly t positions,
// A_k = sum_{t=k..4} C(t,k)*x_t  => solve for x_t and answer is x_{4-D}.
// Works for any alphabet; only equality matters.
//
// Input:
// n D
// n lines of 4-char PINs (digits/letters or any visible bytes; spaces not allowed in PIN)
// Output: number of pairs with Hamming distance exactly D
//
// O(n * 16) time, O(n) memory.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, D;
    if (!(cin >> n >> D)) return 0;
    vector<string> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    // 16 masks (4-bit). Bit i=1 means "keep position i"; 0 means wildcard.
    // Key encoding: high 8 bits store mask (for safety), remaining bytes pack kept chars in order i=0..3.
    // This guarantees uniqueness per (mask, kept-chars).
    array<unordered_map<unsigned long long, int>, 16> maps;
    for (int m = 0; m < 16; ++m) {
        // Heuristic reserve: about n / (#keys per mask). Keep it simple but safe.
        // For m==0, there is 1 key; for others, up to n distinct.
        if (m == 0) maps[m].reserve(1);
        else maps[m].reserve(min(n, 1<<16)); // avoid huge rehashes
    }

    auto make_key = [](const string& s, int mask)->unsigned long long {
        unsigned long long key = (unsigned long long)(mask & 0xFF) << 56; // mask in top 8 bits
        int shift = 0;
        for (int i = 0; i < 4; ++i) if (mask & (1<<i)) {
            key |= (unsigned long long)(unsigned char)s[i] << shift;
            shift += 8;
        }
        return key;
    };

    for (const string& s : a) {
        for (int m = 0; m < 16; ++m) {
            unsigned long long k = make_key(s, m);
            ++maps[m][k];
        }
    }

    long long A[5] = {0,0,0,0,0};
    auto popc = [](int x){ return __builtin_popcount((unsigned)x); };

    for (int m = 0; m < 16; ++m) {
        int k = popc(m);
        long long sum = 0;
        for (auto &it : maps[m]) {
            long long c = it.second;
            sum += c * (c - 1) / 2;
        }
        A[k] += sum;
    }

    // Invert:
    // x4 = A4
    // x3 = A3 - 4*x4
    // x2 = A2 - 3*x3 - 6*x4
    // x1 = A1 - 2*x2 - 3*x3 - 4*x4
    // x0 = A0 - x1 - x2 - x3 - x4
    long long x[5];
    x[4] = A[4];
    x[3] = A[3] - 4LL * x[4];
    x[2] = A[2] - 3LL * x[3] - 6LL * x[4];
    x[1] = A[1] - 2LL * x[2] - 3LL * x[3] - 4LL * x[4];
    x[0] = A[0] - x[1] - x[2] - x[3] - x[4];

    int t = 4 - D; // pairs that agree on exactly t positions
    if (t < 0 || t > 4) { cout << 0 << '\n'; return 0; }
    cout << x[t] << '\n';
    return 0;
}

• Subtask 1: 100 / 100