TopCoder SRM 457 Div1 Medium TheHexagonsDivOne

問題

 A B
C D E
 F G

六角形が7個ならんだ図形に、以下の条件を満たすように数字を書き入れる。(上のA〜Gに数字を入れる)
それぞれの数字は1〜2*nの整数であり、
全て互いに異なり、かつ任意の隣合う数字a,bについてa%n≠b%nが成り立つ。


ただし、回転して重なるものは同一とみなすものとする。

制約条件

n≦150

方針

まずは回転を無視して考える。
mod nで同じ数字がいくつあるかのパターンを深さ優先探索により全て求める。
それぞれのパターンに対して、順列・組み合わせを使ってそのパターンを満たす数字の産め方が何通りあるかを求めて足し合わせる。


最後に、全てのパターンが6回ずつ数えられているので、6で割る。

ソースコード

ll C(int n,int k){
  ll res=1;
  rep(i,k)res*=n-i,res/=i+1;
  return res;
}
ll P(int n,int k){
  ll res=1;
  rep(i,k)res*=n-i;
  return res;
}
ll ans;
int m[7];
void rec(int c,int n){
  if(c==7){
    rep(i,6)if(m[i]==m[(i+1)%6]||m[i]==m[6])return;
    int use[7]={},mx=0;
    rep(i,7)if(m[i]>=0)mx=max(mx,m[i]), use[m[i]]++;
    rep(i,7)if(use[i]>2||i<mx&&!use[i])return;
    ll tmp=C(n,mx+1);
    rep(i,mx+1)tmp*=P(2,use[i]);
    ans+=tmp;
    return;
  }
  rep(i,min(n,7)){
    m[c]=i;
    rec(c+1,n);
  }
}
class TheHexagonsDivOne {
  public:
  long long count(int n) {
    ans=0;
    rec(0,n);
    return ans/6;
  }
};