Submission #872990

#	Time	Username	Problem	Language	Result	Execution time	Memory
872990		tsumondai	Set (COCI21_set)	C++14	110 / 110	124 ms	27732 KiB

Main

/*
Cho một số lượng các lá bài được biểu diễn bằng giá trị 1 2 3, một bộ ba unorder tripet là một cặp mà trong đó
các phần tử ở vị trí tương ứng đều bằng nhau hoặc khác nhau đôi một.
*/


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

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME  (1.0 * clock() / CLOCKS_PER_SEC)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 1e6 + 5;
 
const int oo = 1e18, mod = 1e9 + 7;

int n, k;
int cnt[N];

struct Z_adjoin_w {
    int x, y;

    Z_adjoin_w () {
        x = y = 0;
    }

    Z_adjoin_w (int _x, int _y) {
        x = _x; y = _y;
    }
} P[N];

const Z_adjoin_w w = Z_adjoin_w(0, 1);
const Z_adjoin_w w2 = Z_adjoin_w(-1, -1);

Z_adjoin_w add (Z_adjoin_w a, Z_adjoin_w b) {
    return Z_adjoin_w(a.x + b.x, a.y + b.y);
}

Z_adjoin_w div_by_3 (Z_adjoin_w a) {
    return Z_adjoin_w(a.x / 3, a.y / 3);
}

Z_adjoin_w mul (Z_adjoin_w a, Z_adjoin_w b) {
    return Z_adjoin_w(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x - a.y * b.y);
}

void modified_FWHT (bool invert) {
    int siz = 1;
    for (int i = 0; i < k; i++) siz *= 3;

    for (int len = 1; len < siz; len *= 3) {
        for (int i = 0; i < siz; i += 3 * len) {
            for (int j = 0; j < len; j++) {
                Z_adjoin_w a = P[i + j + len * 0];
                Z_adjoin_w b = P[i + j + len * 1];
                Z_adjoin_w c = P[i + j + len * 2];
                if (invert == 0) {
                    P[i + j + len * 0] = add(a, add(b, c));
                    P[i + j + len * 1] = add(a, add(mul(b, w), mul(c, w2)));
                    P[i + j + len * 2] = add(a, add(mul(b, w2), mul(c, w)));
                } else {
                    P[i + j + len * 0] = div_by_3(add(a, add(b, c)));
                    P[i + j + len * 1] = div_by_3(add(a, add(mul(b, w2), mul(c, w))));
                    P[i + j + len * 2] = div_by_3(add(a, add(mul(b, w), mul(c, w2))));
                }
            }
        }
    }
}

void calc () {
    int siz = 1;
    for (int i = 0; i < k; i++) siz *= 3;

    modified_FWHT(0);
    for (int i = 0; i < siz; i++) {
        P[i] = mul(P[i], P[i]);
    }
    modified_FWHT(1);

    int sol = 0;
    for (int i = 0; i < siz; i++) {
        int val = i, comp = 0, pot = 1;
        for (int j = 0; j < k; j++) {
            comp += (3 - val % 3) % 3 * pot;
            val /= 3;
            pot *= 3;
        }
        sol += cnt[i] * (P[comp].x - 1);
    }
    cout << sol / 6;
}

signed main () {
    //ios_base::sync_with_stdio(false);
    //cin.tie(0);
    scanf("%d%d", &n, &k);
    getchar();
    for (int i = 0; i < n; i++) {

        int val = 0;
        for (int j = 0; j < k; j++) {
            char c = getchar();
            val = val * 3 + c - '1';
        }
        getchar();

        P[val] = Z_adjoin_w(1, 0);
        cnt[val]++;
    }
    calc();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:107:13: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
  107 |     scanf("%d%d", &n, &k);
      |            ~^     ~~
      |             |     |
      |             int*  long long int*
      |            %lld
Main.cpp:107:15: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
  107 |     scanf("%d%d", &n, &k);
      |              ~^       ~~
      |               |       |
      |               int*    long long int*
      |              %lld
Main.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |     scanf("%d%d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~

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