Submission #488555

#	Time	Username	Problem	Language	Result	Execution time	Memory
488555		rainboy	Set (COCI21_set)	C11	110 / 110	126 ms	15224 KiB

Main

#include <stdio.h>

#define K	12
#define N	531441

void fwt(long long (*aa)[2], int n) {
	if (n > 1) {
		int m = n / 3, i;

		fwt(aa, m), fwt(aa + m, m), fwt(aa + m * 2, m);
		for (i = 0; i < m; i++) {
			long long a0 = aa[i][0], a1 = aa[i][1];
			long long b0 = aa[i + m][0], b1 = aa[i + m][1];
			long long c0 = aa[i + m * 2][0], c1 = aa[i + m * 2][1];

			aa[i][0] = a0 + b0 + c0, aa[i][1] = a1 + b1 + c1;
			aa[i + m][0] = a0 - b1 + (c1 - c0), aa[i + m][1] = a1 + (b0 - b1) - c0;
			aa[i + m * 2][0] = a0 + (b1 - b0) - c1, aa[i + m * 2][1] = a1 - b0 + (c0 - c1);
		}
	}
}

void ifwt(long long (*aa)[2], int n) {
	if (n > 1) {
		int m = n / 3, i;

		for (i = 0; i < m; i++) {
			long long a0 = aa[i][0], a1 = aa[i][1];
			long long b0 = aa[i + m][0], b1 = aa[i + m][1];
			long long c0 = aa[i + m * 2][0], c1 = aa[i + m * 2][1];

			aa[i][0] = (a0 + b0 + c0) / 3, aa[i][1] = (a1 + b1 + c1) / 3;
			aa[i + m][0] = (a0 + (b1 - b0) - c1) / 3, aa[i + m][1] = (a1 - b0 + (c0 - c1)) / 3;
			aa[i + m * 2][0] = (a0 - b1 + (c1 - c0)) / 3, aa[i + m * 2][1] = (a1 + (b0 - b1) - c0) / 3;
		}
		ifwt(aa, m), ifwt(aa + m, m), ifwt(aa + m * 2, m);
	}
}

int main() {
	static long long aa[N][2];
	int n, k, i;
	long long ans;

	scanf("%d%d", &n, &k);
	while (n--) {
		static char cc[K + 1];
		int h;

		scanf("%s", cc);
		i = 0;
		for (h = 0; h < k; h++)
			i = i * 3 + (cc[h] - '1');
		aa[i][0]++;
	}
	ans = 0;
	for (i = 0; i < N; i++) {
		ans -= (long long) aa[i][0] * aa[i][0] * aa[i][0];
		ans += (long long) aa[i][0] * (aa[i][0] - 1) * (aa[i][0] - 2);
	}
	fwt(aa, N);
	for (i = 0; i < N; i++) {
		long long a0 = aa[i][0], a1 = aa[i][1];
		long long a = a1 * a1 * a1, b = a0 * a1 * a1 * 3, c = a0 * a0 * a1 * 3, d = a0 * a0 * a0;

		aa[i][0] = d - b + a, aa[i][1] = c - b;
	}
	ifwt(aa, N);
	ans += aa[0][0], ans /= 6;
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:45:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |  scanf("%d%d", &n, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:50:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |   scanf("%s", cc);
      |   ^~~~~~~~~~~~~~~

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