Submission #870987

#	Time	Username	Problem	Language	Result	Execution time	Memory
870987		rainboy	Lucky Numbers (RMI19_lucky)	C11	100 / 100	34 ms	16472 KiB

lucky

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

#define N	100000
#define H_	17	/* H_ = ceil(log2(N)) */
#define N_	(1 << H_)
#define MD	1000000007

int st[N_ * 2][4][4], n_;

void put(int i, int d) {
	memset(st[i], 0, sizeof st[i]);
	if (d == 0)
		st[i][0][0] = 1;
	else if (d == 1)
		st[i][0][1] = 1, st[i][0][2] = 1;
	else
		st[i][0][0] = 1, st[i][0][2] = d - 1, st[i][0][3] = 1;
	if (d == 0)
		st[i][1][0] = 1;
	else if (d == 1)
		st[i][1][1] = 1, st[i][1][2] = 1;
	else if (d == 2)
		st[i][1][0] = 1, st[i][1][2] = 1, st[i][1][3] = 1;
	else if (d == 3)
		st[i][1][2] = 2, st[i][1][3] = 1;
	else
		st[i][1][0] = 1, st[i][1][2] = d - 2, st[i][1][3] = 1;
	st[i][2][2] = 9, st[i][2][3] = 1;
	st[i][3][2] = 8, st[i][3][3] = 1;
}

void pul(int i) {
	int l = i << 1, r = l | 1, u, v, w;

	memset(st[i], 0, sizeof st[i]);
	for (u = 0; u < 4; u++)
		for (v = u < 2 ? 0 : 2; v < 4; v++)
			for (w = v < 2 ? 0 : 2; w < 4; w++)
				st[i][u][w] = (st[i][u][w] + (long long) st[l][u][v] * st[r][v][w]) % MD;
}

void build(char *cc, int n) {
	int i;

	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	for (i = 0; i < n; i++)
		put(n_ + i, cc[i]);
	for (i = n_ - 1; i > 0; i--)
		pul(i);
}

void update(int i, int d) {
	put(i += n_, d);
	while (i > 1)
		pul(i >>= 1);
}

void apply(int *aa, int bb[][4]) {
	static int cc[4];
	int u, v;

	memset(cc, 0, sizeof cc);
	for (u = 0; u < 4; u++)
		for (v = u < 2 ? 0 : 2; v < 4; v++)
			cc[v] = (cc[v] + (long long) aa[u] * bb[u][v]) % MD;
	memcpy(aa, cc, sizeof cc);
}

int query(int l, int r) {
	static int qu[H_ + 1], aa[4];
	int cnt, u, x;

	memset(aa, 0, sizeof aa), aa[0] = 1;
	cnt = 0;
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			apply(aa, st[l++]);
		if ((r & 1) == 0)
			qu[cnt++] = r--;
	}
	while (cnt--)
		apply(aa, st[qu[cnt]]);
	x = 0;
	for (u = 0; u < 4; u++)
		x = (x + aa[u]) % MD;
	return x;
}

int main() {
	static char cc[N + 1];
	int n, q, i, l, r, d;

	scanf("%d%d%s", &n, &q, cc);
	for (i = 0; i < n; i++)
		cc[i] -= '0';
	build(cc, n);
	printf("%d\n", query(0, n - 1));
	while (q--) {
		int t;

		scanf("%d", &t);
		if (t == 1) {
			scanf("%d%d", &l, &r), l--, r--;
			printf("%d\n", query(l, r));
		} else {
			scanf("%d%d", &i, &d), i--;
			update(i, d);
		}
	}
	return 0;
}

Compilation message (stderr)

lucky.c: In function 'main':
lucky.c:96:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |  scanf("%d%d%s", &n, &q, cc);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
lucky.c:104:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |   scanf("%d", &t);
      |   ^~~~~~~~~~~~~~~
lucky.c:106:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |    scanf("%d%d", &l, &r), l--, r--;
      |    ^~~~~~~~~~~~~~~~~~~~~
lucky.c:109:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |    scanf("%d%d", &i, &d), i--;
      |    ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 27 / 27
• Subtask 5: 9 / 9
• Subtask 6: 27 / 27