Submission #491136

#	Time	Username	Problem	Language	Result	Execution time	Memory
491136		rainboy	Semafor (COI20_semafor)	C11	100 / 100	100 ms	412 KiB

semafor

#include <stdio.h>
#include <string.h>

#define N	100
#define MD	1000000007
#define B	32

int count[B];
int mask[] = { 10, 2, 9, 7, 18, 21, 12, 3, 29, 23 };
int vch5[] = { 1, 5, 10, 10, 5, 1 };
int vch10[] = { 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1 };

int inv(int a) {
	return a == 1 ? 1 : (long long) inv(a - MD % a) * (MD / a + 1) % MD;
}

void init() {
	int b, i;

	for (b = 1; b < B; b++)
		count[b] = count[b & b - 1] + 1;
	for (i = 0; i <= 5; i++)
		vch5[i] = inv(vch5[i]);
	for (i = 0; i <= 10; i++)
		vch10[i] = inv(vch10[i]);
}

void mult(int aa[][N], int bb[][N], int cc[][N], int n) {
	int i, j, k;

	for (i = 0; i < n; i++)
		memset(cc[i], 0, n * sizeof *cc[i]);
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++) {
			int a = aa[i][j];

			if (a == 0)
				continue;
			for (k = 0; k < n; k++) {
				int b = bb[j][k];

				if (b != 0)
					cc[i][k] = (cc[i][k] + (long long) a * b) % MD;
			}
		}
}

void power(int aa[][N], int pp[][N], int tt[][N], int n, long long k) {
	if (k == 0) {
		int i;

		for (i = 0; i < n; i++)
			memset(pp[i], 0, n * sizeof *pp[i]), pp[i][i] = 1;
		return;
	}
	if (k % 2 == 0) {
		power(aa, tt, pp, n, k / 2);
		mult(tt, tt, pp, n);
	} else {
		power(aa, pp, tt, n, k / 2);
		mult(pp, pp, tt, n);
		mult(tt, aa, pp, n);
	}
}

int main() {
	static int aa[N][N], bb[N][N], cc[N][N], pp[N][N], tt[N][N];
	int n, m, s, i, j, c;
	long long k, l;

	init();
	scanf("%d%lld%lld%d", &m, &k, &l, &s), n = m == 1 ? 10 : 100;
	for (c = 0; c <= m * 5; c++) {
		if (c < m * 5)
			aa[c][c + 1] = m * 5 - c;
		if (c > 0)
			aa[c][c - 1] = c;
	}
	power(aa, pp, tt, m * 5 + 1, l);
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			if (m == 1) {
				c = count[mask[i] ^ mask[j]];
				bb[i][j] = (long long) pp[0][c] * vch5[c] % MD;
			} else {
				c = count[mask[i / 10] ^ mask[j / 10]] + count[mask[i % 10] ^ mask[j % 10]];
				bb[i][j] = (long long) pp[0][c] * vch10[c] % MD;
			}
	power(bb, cc, tt, n, k / l);
	power(aa, pp, tt, m * 5 + 1, k % l);
	for (j = 0; j < n; j++) {
		int ans;

		ans = 0;
		for (i = 0; i < n; i++) {
			int x;

			if (m == 1) {
				c = count[mask[i] ^ mask[j]];
				x = (long long) pp[0][c] * vch5[c] % MD;
			} else {
				c = count[mask[i / 10] ^ mask[j / 10]] + count[mask[i % 10] ^ mask[j % 10]];
				x = (long long) pp[0][c] * vch10[c] % MD;
			}
			ans = (ans + (long long) cc[s][i] * x) % MD;
		}
		printf("%d\n", ans);
	}
	return 0;
}

Compilation message (stderr)

semafor.c: In function 'init':
semafor.c:21:26: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   21 |   count[b] = count[b & b - 1] + 1;
      |                        ~~^~~
semafor.c: In function 'main':
semafor.c:72:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |  scanf("%d%lld%lld%d", &m, &k, &l, &s), n = m == 1 ? 10 : 100;
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 15 / 15
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 15 / 15
• Subtask 6: 40 / 40