취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 3835번 문제인 Alphabet Soup이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/3835 

원형으로 알파벳을 놓을 수 있는 각도들이 정해져있을 때 얼마나 다양하게 알파벳을 배치할 수 있는가를 묻는 문제이다.

먼저 수프를 회전했을 때 처음과 같은 각도들의 배치가 나오게 하는 최소 각도를 구하자. 이는 KMP 알고리즘의 fail함수를 활용해 구해줄 수 있다.

그 다음으로 그만큼의 각도에 놓을 수 있는 총 알파벳의 개수를 이용해 존재할 수 있는 구간의 경우의 수를 구하고, 그러한 구간을 원모양으로 배치하는 경우의 수를 번사이드 보조정리를 이용하여 구하는 것으로 문제를 해결할 수 있다.

1,000,000,007로 나눈 나머지를 구하는 것이 아닌 100,000,007로 나눈 나머지를 구하는 문제임에 유의하자.

또한, 수프를 뒤집어엎으면 안된다는 점에 유의하자.

아래는 제출한 소스코드이다.

#define MOD 100000007
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;

int arr[360000];
int pi[360000];

ll gcd(ll x, ll y) {
	if (y == 0) return x;
	return gcd(y, x % y);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	ll N, M; cin >> N >> M;
	while (N >= 0) {
		memset(arr, 0, sizeof(arr));
		memset(pi, 0, sizeof(pi));
		for (int m = 0; m < M; m++) {
			int x; cin >> x;
			arr[x] = 1;
		}

		for (int i = 0; i < 360000; i++) {
			int idx = i;
			while (idx > 0) {
				if (arr[pi[idx - 1]] == arr[i]) break;
				idx = pi[idx - 1];
			}
			if (idx == 0) pi[i] = 0;
			else pi[i] = pi[idx - 1] + 1;
		}
		ll L = 360000 - pi[359999];
		if (360000 % L != 0) L = 360000;
		ll beads = 360000 / L;

		ll colors = 1;
		for (int l = 0; l < L; l++) {
			if (arr[l]) colors = (colors * N) % MOD;
		}

		ll total = 0;
		for (ll i = 1; i <= beads; i++) {
			ll cur = gcd(i, beads);
			ll ret = 1;
			ll CC = colors;
			while (cur > 0) {
				if (cur & 1) ret = (ret * CC) % MOD;
				CC = (CC * CC) % MOD;
				cur >>= 1;
			}
			total = (total + ret) % MOD;
		}

		ll invbeads = 1;
		int p = 100000005;
		while (p > 0) {
			if (p & 1) invbeads = (beads * invbeads) % MOD;
			beads = (beads * beads) % MOD;
			p >>= 1;
		}

		cout << (total * invbeads) % MOD << '\n';
		cin >> N >> M;
	}
}