POJ-2409 : Let it Bead

問題概要

s個のビーズで数珠を作る場合の数を求める問題。色はc色を自由に選べる。s*c <= 32。

解法

ポリアなどで反転を考えない場合の答を出す。それから左右対称な場合の数以外についてだけ2で割ればよい。左右対称な場合の数を数え上げるのは簡単。

acceptされたコード

#include <cstdio>
#include <map>
#include <algorithm>
#include <vector>
using namespace std;

typedef long long int64;
const int64 MOD = int64( 1e9 + 7 );

int S, C;

int64 calcPow(int64 x, int64 n, int64 mod = MOD) {
	int64 ret = 1;
	for (; n; n >>= 1, x = x * x % mod) if (n&1) {
		ret = ret * x % mod;
	}
	return ret;
}

int findDivisors(int64 x, vector<int64>& divs) {
	divs.clear();
	// if x is large, divs.reserve(some value)
	for (int64 i = 1; i*i <= x; ++i) if(x%i == 0) {
		divs.push_back(i);
		if ( i*i != x ) {
			divs.push_back(x/i);
		}
	}
	sort(divs.begin(), divs.end());
	return (int)divs.size();
}

map<int64, int> factorize(int64 x) {
	map<int64, int> ret;
	for (int64 i = 2; i*i <= x; ++i) {
		for ( ; x%i == 0; ++ret[i], x/=i) ;
	}
	if (x != 1) {
		++ret[x];
	}
	return ret;
}

int64 calcCircularPermutation(int64 n, int64 numColor) {
	map<int64, int> primeFactors = factorize(n);
	vector<int64> divisors;
	findDivisors(n, divisors);

	int64 ans = 0;
	for (int i = 0; i < int(divisors.size()); ++i) {
		int64 phi = divisors[i];
		for (map<int64,int>::iterator itr = primeFactors.begin(); itr != primeFactors.end(); ++itr) {
			const int64 p = itr->first;
			if (divisors[i] % p == 0) {
				phi = phi / p * (p - 1);
			}
		}
		ans = (ans + phi * calcPow(numColor, n / divisors[i])) % MOD;
	}

	return ans * calcPow(n, MOD - 2) % MOD;
}

int64 calcNecklacePermutation(int64 n, int64 numColor) {
	int64 ans = calcCircularPermutation(n, numColor);
	int64 revCount = 0; 
	if (n&1) {
		revCount = numColor * calcPow(numColor, n / 2) % MOD;
	}
	else {
		revCount = calcPow(numColor, n / 2) % MOD;
		revCount = (revCount + numColor * (numColor - 1) / 2 % MOD * calcPow(numColor, n / 2 - 1)) % MOD;
	}

	ans = (ans - revCount + MOD) * calcPow(2, MOD - 2) % MOD; 
	ans = (ans + revCount) % MOD;
	return ans;
}

bool init() {
	scanf("%d%d", &C, &S);
	return C > 0;
}

int solve() {
	return int(calcNecklacePermutation(S, C));
}

int main() {
	for (;init();) {
		printf("%d\n", solve());
	}
	return 0;
}