TopCoder SRM423 Div1Hard
問題
N*Nのボードがあり、色の異なるチェッカーがある。色iのチェッカーはcheckers[i]個ある。回転させて重なる配置を同じ配置と考えるとき、何通りの異なる配置があるか。
解法
90°回転で重なるものがA通り、180°回転で重なる(かつ90°回転で重ならないもの)がB通り、180°回転でも重ならないものがC通りあるとき、A+B/2+C/4通りが答えである。
C(a,b)を求めるのが必要でかつけっこう大変であるが、1234567891が素数のため、予め1〜100000について逆元を求めておけばC(a,b)はすぐに求まる。
回転によって重なるものの数は、どのマスの状態が一致しないといけないかを考えると、偶数の場合は自明である(マス数、チェッカー数をそれぞれ2,4で割ればよい。割り切れない場合は0通り)。
奇数の場合は、中央のマスが回転しても動かない。チェッカー数が奇数のものは、1個だけそこに押し込むと偶数になるため回転対称のものの数が求まる。奇数のものが複数あると押し込み切れないため無理である。
コード
#include <vector> using namespace std; #define MOD 1234567891 class TheBeautifulBoard { int rev[100001]; long long make_rev(long long A) { long long B = 1; while(A>1){ long long mul = MOD / A; A = MOD % A; B *= mul; B %= MOD; B = (MOD - B) % MOD; } return B; } long long C(long long A, int B) { if(A<B) return 0; if(A==0) return 1; //C(A, B) long long ret = 1; for(int i=0;i<B;i++){ ret *= (A-i)%MOD; ret %= MOD; } for(int i=1;i<=B;i++){ ret *= rev[i]; ret %= MOD; } return ret; } static const long long per2 = (MOD+1)/2; long long div2(long long X) { return (X*per2)%MOD; } public: int count(int N, vector<int> chk) { for(int i=1;i<=100000;i++) rev[i] = make_rev(i); long long sym90=0, sym180=0, total=0; long long sum; total = 1; sum = N * (long long)N; for(int i=0;i<chk.size();i++){ total = (total * C(sum, chk[i])) % MOD; sum -= chk[i]; } if(N%2==1){ int flg = -1; for(int i=0;i<chk.size();i++){ if(chk[i]%2==1){ if(flg==-1) flg = i; else flg = -2; } } if(flg==-2) goto rt; if(flg!=-1) chk[flg]--; } sym90 = 1; sum = N * (long long)N / 4; for(int i=0;i<chk.size();i++){ if(chk[i]%4!=0){ sym90 = 0; break; } sym90 = (sym90 * C(sum, chk[i]/4)) % MOD; sum -= chk[i]/4; } sym180 = 1; sum = N * (long long)N / 2; for(int i=0;i<chk.size();i++){ if(chk[i]%2!=0){ sym180 = 0; break; } sym180 = (sym180 * C(sum, chk[i]/2)) % MOD; sum -= chk[i]/2; } rt: total = (total - sym180 + MOD) % MOD; sym180 = (sym180 - sym90 + MOD) % MOD; //printf("%lld %lld %lld\n", sym90, sym180, total); //printf("%lld\n", (sym90 + div2(sym180) + div2(div2(total)))); return (int)( (sym90 + div2(sym180) + div2(div2(total))) % MOD); } };