Submission #65176821

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <string.h>
#define MOD_BY 998244353
int add(int a, int b) {
  return a + b - MOD_BY * (a + b >= MOD_BY);
}
int mul(int a, int b) {
  return (int)((long long)a * b % MOD_BY);
}
void matmul(int out[49][49], int a[49][49], int b[49][49]) {
  int i, j, k;
  memset(out, 0, sizeof(int[49][49]));
  for (k = 0; k < 49; k++) {
    for (i = 0; i < 49; i++) {
      for (j = 0; j < 49; j++) {
        out[i][j] = add(out[i][j], mul(a[i][k], b[k][j]));
      }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

#define MOD_BY 998244353

int add(int a, int b) {
	return a + b - MOD_BY * (a + b >= MOD_BY);
}

int mul(int a, int b) {
	return (int)((long long)a * b % MOD_BY);
}

void matmul(int out[49][49], int a[49][49], int b[49][49]) {
	int i, j, k;
	memset(out, 0, sizeof(int[49][49]));
	for (k = 0; k < 49; k++) {
		for (i = 0; i < 49; i++) {
			for (j = 0; j < 49; j++) {
				out[i][j] = add(out[i][j], mul(a[i][k], b[k][j]));
			}
		}
	}
}

int delta[4][256][49][49];

int main(void) {
	int i, j;
	int T, tc;
	for (i = 0; i < 4; i++) {
		for (j = 0; j < 49; j++) {
			delta[i][0][j][j] = 1;
		}
	}
	for (i = 0; i < 7; i++) {
		for (j = 0; j < 7; j++) {
			if (i == 6 && j == 6) {
				delta[0][1][i * 7 + j][i * 7 + j] = 52;
			} else if (i == 6) {
				delta[0][1][i * 7 + j][i * 7 + j] = 51;
				delta[0][1][i * 7 + j][i * 7 + (j + 1)] = 1;
			} else if (j == 6) {
				delta[0][1][i * 7 + j][i * 7 + j] = 51;
				delta[0][1][i * 7 + j][(i + 1) * 7 + j] = 1;
			} else {
				delta[0][1][i * 7 + j][i * 7 + j] = 50;
				delta[0][1][i * 7 + j][(i + 1) * 7 + j] = 1;
				delta[0][1][i * 7 + j][i * 7 + (j + 1)] = 1;
			}
		}
	}
	for (i = 2; i < 256; i++) {
		matmul(delta[0][i], delta[0][i - 1], delta[0][1]);
	}
	for (i = 1; i < 4; i++) {
		matmul(delta[i][1], delta[i - 1][255], delta[i - 1][1]);
		for (j = 2; j < 256; j++) {
			matmul(delta[i][j], delta[i][j - 1], delta[i][1]);
		}
	}
	if (scanf("%d", &T) != 1) return 1;
	for (tc = 0; tc < T; tc++) {
		int buf[3][49][49];
		int N;
		if (scanf("%d", &N) != 1) return 1;
		matmul(buf[0], delta[0][N & 0xff], delta[1][(N >> 8) & 0xff]);
		matmul(buf[1], buf[0], delta[2][(N >> 16) & 0xff]);
		matmul(buf[2], buf[1], delta[3][(N >> 24) & 0xff]);
		printf("%d\n", buf[2][0 * 7 + 0][6 * 7 + 6]);
	}
	return 0;
}

/*

0 <= m < 6, 0 <= n < 6
[m][n] -> [m + 1][n] x 1, [m][n + 1] x 1, [m][n] x 50
[m][6] -> [m + 1][6] x 1, [m][6] x 51
[6][n] -> [6][n + 1] x 1, [6][n] x 51
[6][6] -> [6][6] x 52

*/

Submission Info

Judge Result