提出 #30091431

---

ソースコード 拡げる

#include <stdio.h>
#include <inttypes.h>
#include <string.h>
 
#define MOD_BY 1000000007
 
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);
}
 
int K;
uint64_t N;
 
int mat[16][16];
 
char status[2][4];
void asumikana(int pos) {
	if(pos >= K) {
		int init = 0, result = 0;
		int i;
		for (i = 0; i < K; i++) {
			if (status[0][i] == 2) init |= 1 << i;
			if (status[1][i]) result |= 1 << i;
		}
		mat[init][result]++;
	} else if (status[0][pos]) {
		asumikana(pos + 1);
	} else {
		status[0][pos] = 1;
		status[1][pos] = 1;
		asumikana(pos + 1);
		status[1][pos] = 0;
		if (pos + 1 < K && !status[0][pos + 1]) {
			status[0][pos + 1] = 1;
			asumikana(pos + 2);
			status[0][pos + 1] = 0;
		}
		status[0][pos] = 0;
	}
}
 
void matmul(int res[16][16], int a[16][16], int b[16][16], int size) {
	static int buf[16][16];
	int i, j, k;
	memset(buf, 0, sizeof(buf));
	for (i = 0; i < size; i++) {
		for (k = 0; k < size; k++) {
			for (j = 0; j < size; j++) {
				buf[i][j] = add(buf[i][j], mul(a[i][k], b[k][j]));
			}
		}
	}
	memcpy(res, buf, sizeof(buf));
}
 
void matpow(int res[16][16], int a[16][16], int b, int size) {
	static int abuf[16][16];
	static int rbuf[16][16];
	int i;
	memcpy(abuf, a, sizeof(abuf));
	memset(rbuf, 0, sizeof(rbuf));
	for (i = 0; i < size; i++) rbuf[i][i] = 1;
	while (b > 0) {
		if (b & 1) matmul(rbuf, rbuf, abuf, size);
		if (b > 1) matmul(abuf, abuf, abuf, size);
		b >>= 1;
	}
	memcpy(res, rbuf, sizeof(rbuf));
}
 
int kitamuraeri[16][16];
 
int main(void) {
	int i, j;
	if (scanf("%d%" SCNu64, &K, &N) != 2) return 1;
	for (i = 0; i < (1 << K); i++) {
		for (j = 0; j < K; j++) {
			status[0][j] = ((i >> j) & 1) * 2;
		}
		asumikana(0);
	}
	matpow(kitamuraeri, mat, N, 1 << K);
	printf("%d\n", kitamuraeri[0][0]);
	return 0;
}

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

#define MOD_BY 1000000007

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);
}

int K;
uint64_t N;

int mat[16][16];

char status[2][4];
void asumikana(int pos) {
	if(pos >= K) {
		int init = 0, result = 0;
		int i;
		for (i = 0; i < K; i++) {
			if (status[0][i] == 2) init |= 1 << i;
			if (status[1][i]) result |= 1 << i;
		}
		mat[init][result]++;
	} else if (status[0][pos]) {
		asumikana(pos + 1);
	} else {
		status[0][pos] = 1;
		status[1][pos] = 1;
		asumikana(pos + 1);
		status[1][pos] = 0;
		if (pos + 1 < K && !status[0][pos + 1]) {
			status[0][pos + 1] = 1;
			asumikana(pos + 2);
			status[0][pos + 1] = 0;
		}
		status[0][pos] = 0;
	}
}

void matmul(int res[16][16], int a[16][16], int b[16][16], int size) {
	static int buf[16][16];
	int i, j, k;
	memset(buf, 0, sizeof(buf));
	for (i = 0; i < size; i++) {
		for (k = 0; k < size; k++) {
			for (j = 0; j < size; j++) {
				buf[i][j] = add(buf[i][j], mul(a[i][k], b[k][j]));
			}
		}
	}
	memcpy(res, buf, sizeof(buf));
}

void matpow(int res[16][16], int a[16][16], int b, int size) {
	static int abuf[16][16];
	static int rbuf[16][16];
	int i;
	memcpy(abuf, a, sizeof(abuf));
	memset(rbuf, 0, sizeof(rbuf));
	for (i = 0; i < size; i++) rbuf[i][i] = 1;
	while (b > 0) {
		if (b & 1) matmul(rbuf, rbuf, abuf, size);
		if (b > 1) matmul(abuf, abuf, abuf, size);
		b >>= 1;
	}
	memcpy(res, rbuf, sizeof(rbuf));
}

int kitamuraeri[16][16];

int main(void) {
	int i, j;
	if (scanf("%d%" SCNu64, &K, &N) != 2) return 1;
	for (i = 0; i < (1 << K); i++) {
		for (j = 0; j < K; j++) {
			status[0][j] = ((i >> j) & 1) * 2;
		}
		asumikana(0);
	}
	matpow(kitamuraeri, mat, N, 1 << K);
	printf("%d\n", kitamuraeri[0][0]);
	return 0;
}

提出情報

ジャッジ結果