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