Submission #8931

#	Time	Username	Problem	Language	Result	Execution time	Memory
8931		ekzm0204	The last wizard (kriii2_T)	C++98	4 / 4	976 ms	83416 KiB

T

#include <stdio.h>
#include <memory.h>
typedef long long LL;
const int MAXN = 10001;
/*
const int M = 5;
const int M2 = 32;
*/
const int M = 10;
const int M2 = 1024;

LL T, N, A;
LL P[MAXN];
LL dat[MAXN][M];
LL MOD = 1000000007;
class MV {
public:
	LL d[M2];
};

int bitcnt[M2];
MV I;
LL mult[MAXN][M2];

void init() {
	int w = 0;
	for (int i = 1; i < M2; i+=i) {
		bitcnt[i] = w++;
	}
	for (int i = 0; i < N; i++) {
		mult[i][0] = 1;
		for (int j = 1; j < M2; j++) {
			int l = (j ^ (j - 1))&j;
			mult[i][j] = (mult[i][j^l] * dat[i][bitcnt[l]]) % MOD;
		}
	}
	for (int i = 0; i < M2; i++) {
		for (int j = 0; j < N; j++) {
			I.d[i] = (I.d[i] + P[j] * mult[j][i]) % MOD;
		}
	}
}

MV multTime(MV A, MV B) {
	MV C;
	memset(&C, 0, sizeof(C));
	for (int i = 0; i<M2; i++) {
		for (int j = i;; j = (j - 1)&i) {
			C.d[i] = (C.d[i] + A.d[j] * B.d[i^j]) % MOD;
			if (j == 0) break;
		}
	}
	return C;
}
MV calcTime(LL T) {
	if (T == 1) return I;
	LL t = T / 2;
	MV half = calcTime(t);
	MV R = multTime(half, half);
	if (T % 2 == 1) R = multTime(R, I);

	return R;
}
int main() {
	scanf("%lld %lld %lld", &T, &N, &A);
	P[0] = A;
	for (int j = 0; j<M; j++) dat[0][j] = 0;

	for (int i = 1; i <= N; i++) {
		scanf("%lld", &P[i]);
		P[0] -= P[i];
		for (int j = 0; j<M; j++) {
			scanf("%lld", &dat[i][j]);
		}
	}
	N++;
	init();

	MV R = calcTime(T);
	LL sol = 0;
	for (int i = 0; i < M2; i++) {
		sol = (sol + R.d[i]) % MOD;
	}
	printf("%lld\n", sol);
	return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 3 / 3