BOJ 14559 - Protocol

* BOJ 14559 - Protocol

[분류 - 수학, 다이나믹 프로그래밍]

  아이디어를 생각하기 어려운 문제..

  구하고자 하는 건 M세대를 거쳐 2^M개의 112345^k꼴로 표현되는 수의 합입니다. x+1 세대의 합을 x 세대로 표현이 가능해야 큰 수 M에 대응할 수 있습니다. 하지만 f(x), g(x)로 x+1을 나타낼 수가 없습니다. 즉, 다른 트릭을 쓰지 않고서는 범위를 줄일 수 없고, 점화식을 구할 수 없습니다.

  (페르마 소정리) 임의의 소수 p에 대해 임의의 양의 정수 x(x<p)에 대해 x의 곱셈 역원은 x^(p-2) mod m입니다. 따라서 112345도 곱셈의 역원이 분명 존재합니다. 이는 112345^(m-2)임을 알 수 있는데 여기서 112345^(m-1)=1 mod m임을 알 수 있습니다. 따라서 m-1의 임의의 약수 k에 대해 112345^k=1이 되는 가장 작은 k를 찾아봅시다. 이 값이 매우 크면 이 방법을 사용할 수 없습니다.

  실제로 112345라는 수에 대해서 가장 작은 k는 167임을 구할 수 있습니다.

  (행렬) 이제 167 x 167 행렬에서 x 세대에서 x+1 세대로 갈 때 승수에 대해서 167로

나눈 나머지로 축약시킬 수 있으므로 점화식을 구할 수 있습니다. 즉 (i, j)에 들어가야하는 값은 x세대 때 j였던 것의 개수가 x+1세대 때 i로 가는 경우의 수로 나타낼 수 있습니다. 간단하게 구하면 x세대 때 j는 f(j)와 g(j)로 두 개의 경우의 수로 나뉘기 때문에 각각 구해줍시다.

, 

  167 x 1 행렬은 초기 0세대에 대한 값이고 167 x 1 행렬 X_M는 M세대 이후의 상태도라고 보시면 됩니다.

#include<cstdio>
#include<cstring>
using ll = long long;
const int L = 167, MOD = 1e9 + 9, P = 112345;
struct _mt {
	int m[L][L];
	_mt() { memset(m, 0, sizeof m); }
	void E() { for (int i = 0; i < L; i++) m[i][i] = 1; }
	_mt operator*(const _mt& o) {
		_mt r;
		int i, j, k;
		for (i = 0; i < L; i++) for (j = 0; j < L; j++) for (k = 0; k < L; k++)
			r.m[i][j] = (r.m[i][j] + (ll)m[i][k] * o.m[k][j]) % MOD;
		return r;
	}
}A, E, X;
_mt _pow(const _mt& a, int n) {
	if (n <= 1) return n % 2 ? a : E;
	_mt h = _pow(a, n >> 1);
	return h * h * (n % 2 ? a : E);
}
int _pow(int a, int n) {
	if (n <= 1) return n % 2 ? a : 1;
	int h = _pow(a, n >> 1);
	return ((ll)h * h % MOD) * (n % 2 ? a : 1) % MOD;
}
int main() {
	E.E();
	int N, M, a, b, c, d, e, f, i, ans = 0;
	scanf("%d%d%d%d%d%d%d%d", &N, &M, &a, &b, &c, &d, &e, &f);
	for (i = 0; i < L; i++) {
		A.m[((ll)a * i * i + (ll)b * i + c) % L][i]++;
		A.m[((ll)d * i * i + (ll)e * i + f) % L][i]++;
	}
	N %= L;
	X = _pow(A, M);
	for (i = 0; i < L; i++)
		ans = (ans + (ll)X.m[i][N] * _pow(P, i)) % MOD;
	printf("%d", ans);
	return 0;
}

※ 벌레 캠프 머시기 알고리즘으로도 풀린다곤 하네요,, 전 모르겟네요~