POJ-1286 : Necklace of Beads
問題概要
3色のビーズを使って数珠が何通り作れるか求める問題。
解法
とりあえず反転を無視して回転対称だけ重複を取り除いた個数をx個とする。これは蟻本で紹介されてる問題そのもの。左右対称な個数をr個とすると、求める個数は(x - r) / 2 + rとなる。左右対称な個数は奇数の場合は簡単で、偶数の場合は対称軸にビーズが乗っている場合と乗っていない場合を考えてやれば解ける。
acceptされたコード
#include <cstdio> #include <vector> #include <map> using namespace std; typedef long long int64; const int MAX_N = 25; int64 pow_binary(int64 x, int n){ int64 ret = 1; for(;n;n>>=1, x = x * x)if(n&1){ ret = ret * x; } return ret; } //xの約数を全て求める。結果はソートされていない。 //計算量O(sqrt(x))。 vector<int64> divisor(int64 x){ vector<int64> ret; for(int64 i=1; i*i <= x; ++i)if(x%i == 0){ ret.push_back(i); if(i*i!=x){ ret.push_back(x/i); } } return ret; } const int MAX_PHI = ::MAX_N; int phi[MAX_PHI + 1]; //phi(n)のテーブルを作る。計算量O(MAX_PHI)よりちょっと重い。 void euler_phi_lookup(){ for(int i=0; i<=MAX_PHI; ++i){ phi[i] = i; } for(int i=2; i<=MAX_PHI; ++i)if(phi[i] == i){ for(int j=i; j<=MAX_PHI; j+=i){ phi[j] = phi[j] / i * (i - 1); } } } //xを素因数分解した結果を返す。 //計算量O(sqrt(x))。 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; } int N; bool visited[MAX_N + 1]; int64 memo[MAX_N + 1]; bool init(){ return scanf("%d", &N), N!=-1; } int64 solve(){ if(visited[N]){ return memo[N]; } visited[N] = true; if(N == 0){ return memo[N] = 0; } int64 ans = 0; //反転無視 map<int64, int> primes = factorize(N); vector<int64> divs = divisor(N); for(int i=0; i<(int)divs.size(); ++i){ ans += phi[divs[i]] * pow_binary(3, N / divs[i]); } ans /= N; //左右対称なものを数える int64 rev = 0; rev += pow_binary(3, (N + 1) / 2); if(N % 2 == 0){ rev += 3 * pow_binary(3, N / 2 - 1); } ans = (ans - rev) / 2 + rev; return memo[N] = ans; } int main(){ euler_phi_lookup(); for(;init();){ printf("%lld\n", solve()); } return 0; }