SRM322 D1M ExtendedDominoes

TopCoder Statistics - Problem Statement
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

ドミノのピースが与えられて，それには表と裏に数字が書いてある．それは反転しても良い．ピースの裏とピースの表が同じ数字の時にくっつけることが出来て，円環になるように最初のピースの表と，最後のピースの裏が同じになるようにする．このようにした時に何通りの分け方が存在するか．

分からなかったので解説を見た．頂点をひと桁の数字とすると，ドミノは辺と見ることができる．反転して使っても良いので無向グラフとなる．このグラフの，一筆書きができる連結成文に分け方を求めるという問題になる．

$i$番目の頂点の次数を$d[i]$として，今その頂点に入ってきたとすると，$d[i]-1$通り出て行く候補がある．出て行った後は入ってきたパスと出て行くパスを消したいので，次数を$d[i]-2$する．後はこれを全ての頂点においてやる．

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <queue>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

class ExtendedDominoes {
  public:
  long long countCycles(vector <string> pieces) {
      int d[10];
      memset(d, 0, sizeof(d));

      rep(i, pieces.size()) {
          rep(j, 2) {
              d[pieces[i][j]-'0']++;
          }
      }

      rep(i, 10) {
          if(d[i] % 2 == 1) return 0;
      }

      ll  ans = 1;
      rep(i, 10) {
          while(d[i]) {
              ans *= (d[i] - 1);
              d[i] -= 2;
          }
      }

      return ans;
  }
};