Submission #135402

#	Time	Username	Problem	Language	Result	Execution time	Memory
135402		imeimi2000	PIN (CEOI10_pin)	C++17	100 / 100	33 ms	8056 KiB

pin

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long llong;

int n, d;
int cnt[16][36 * 36 * 36 * 36];
int tr[256];
char S[50001][5];

llong nCr[9][9];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    nCr[0][0] = 1;
    for (int i = 1; i < 9; ++i) {
        for (int j = 0; j <= i; ++j) {
            if (j > 0) nCr[i][j] += nCr[i - 1][j - 1];
            if (j < i) nCr[i][j] += nCr[i - 1][j];
        }
    }
    for (int i = 0; i < 10; ++i) tr[i + '0'] = i;
    for (int i = 0; i < 26; ++i) tr[i + 'a'] = i + 10;
    cin >> n >> d;
    d = 4 - d;
    for (int i = 0; i < n; ++i) {
        cin >> S[i];
        for (int j = 0; j < 16; ++j) {
            int val = 0;
            for (int k = 0; k < 4; ++k) {
                if ((j >> k) & 1) {
                    val *= 36;
                    val += tr[S[i][k]];
                }
            }
            ++cnt[j][val];
        }
    }
    llong ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 16; ++j) {
            int val = 0, bit = 0;
            for (int k = 0; k < 4; ++k) {
                if ((j >> k) & 1) {
                    val *= 36;
                    val += tr[S[i][k]];
                    ++bit;
                }
            }
            if (d <= bit) {
                if ((bit - d) & 1) ans -= nCr[bit][bit - d] * cnt[j][val];
                else ans += nCr[bit][bit - d] * cnt[j][val];
            }
        }
    }
    printf("%lld\n", ans / 2);
    return 0;
}

Compilation message (stderr)

pin.cpp: In function 'int main()':
pin.cpp:35:38: warning: array subscript has type 'char' [-Wchar-subscripts]
                     val += tr[S[i][k]];
                                      ^
pin.cpp:48:38: warning: array subscript has type 'char' [-Wchar-subscripts]
                     val += tr[S[i][k]];
                                      ^

• Subtask 1: 100 / 100