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