kmjp's blog

競技プログラミング参加記です

Golden Week Contest 2015: E - シフト塗り分け

配点の割に正答者が激しく少ない問題。
http://gwcontest2015.contest.atcoder.jp/tasks/gw2015_e

問題

K色のボールをN個並べる並べ方はK^N通りある。
このうち、パラメータLに対し、連続するL個をシフトすることを繰り返して同じ並びにできる並べ方は同一と見なす。
この時、ボールの並べ方は何通りとなるか。

解法

Editorialを見て回答。

  • N==Lの時
    • ポリアの数え上げ定理そのまま。蟻本第2版 p269を参照。
  • Lが偶数の時
    • シフトを1個ずらした2か所に1回ずつ行うと、(L+1)要素を2回シフトする動作が行える。繰り返すと(L+1)要素を1回シフトする処理も再現できる。
    • L要素及び(L+1)要素のシフトができると、任意の2要素をスワップできる。
    • つまり、結局任意の並びに出来るので、並べ替えて同じになる並びはすべて同一であり、結局はN個をK色から選ぶ重複組み合わせの数H(K,N)となる。
  • Lが奇数の時
    • こちらは(L+1)要素の2回シフトは再現できるが、(L+1)が偶数なので1回シフトは再現できない。
    • よって、この範囲で再現できるのは要素の偶置換のみになる。
    • 1対でも同じ色のボールがあれば、(それを入れ替えるのが実質奇置換と見なせるので)任意の並び方ができる。
    • 逆に全て異なる色の場合、同じボールの組み合わせについて互いに並べ替えられない2通りの並びができる。
    • よってH(K,N)+C(K,N) (全て異なる色の場合だけ2重にカウントするので、C(K,N)を足す)
ll N,K,L;
ll mo=1000000007;
const int prime_max = 1000005;
int NP,prime[100000],divp[prime_max];

ll modpow(ll a, ll n = mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void cprime() {
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		//M[i]=NP;
		prime[NP++]=i;
		for(ll j=1LL*i*i;j>i&&j<prime_max;j+=i) divp[j]=i;
	}
}

vector<ll> enumdiv(ll n) {
	vector<ll> S;
	for(ll i=1;i*i<=n;i++) if(n%i==0) {S.push_back(i); if(i*i!=n) S.push_back(n/i); }
	sort(S.begin(),S.end());
	return S;
}

ll combi(ll N_, ll C_) {
	const int NUM_=2000001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}
ll hcomb(int P_,int Q_) { return (P_==0&&Q_==0)?1:combi(P_+Q_-1,Q_);}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cprime();
	cin>>N>>K>>L;
	
	if(L==N) {
		auto divs=enumdiv(L);
		ll ret=0;
		FORR(r,divs) {
			int phi=r;
			FOR(i,NP) {
				if(prime[i]>r) break;
				if(r%prime[i]==0) phi = phi/prime[i]*(prime[i]-1);
			}
			(ret += phi * modpow(K,N/r))%=mo;
		}
		cout<< ret*modpow(N) % mo << endl;
	}
	else if(L%2==0) {
		cout<<hcomb(K,N)<<endl;
	}
	else {
		cout<<(hcomb(K,N)+combi(K,N))%mo<<endl;
	}
	
}

まとめ

実装はともかく、こんな考察本番に出来ないよ…。