AtCoder ARC #009 : C - 高橋君、24歳

続いてC。
Smallセットはすぐに思いついて解けたのだが、Largeの数の大きさにかなり途方に暮れた。
最終的に解けたが、ネットで一部知らない処理を検索しながらだった。

http://arc009.contest.atcoder.jp/tasks/arc009_3

N個を並べ替えて、K個が元と別の場所にくる組み合わせ数を求める。
まず、smallでは以下の式で解ける。

s64 calc(s64 n,s64 k) {
	s64 re;
	if(n<=0) return 0;
	if(k==1) return 0;
	if(k==0) return 1;
	if(k<0) return 0;
	
	return (((n-1)-(k-2))*calc(n-1,k-2) + (k-1)*calc(n-1,k-1) + calc(n-1,k))%1777777777;
}

1個だけ元と違うことはありえないので0通り、0個元と違う＝全部元と同じ場所は1通り。
漸化式を用いると、kが２以上の時は次の和になる。

(n-1)個中(k-2)個が別の手紙を受け取っており、新たなn個目が正しい手紙を受け取っていた( (n-1)-(k-2) )個の手紙と入れ違ってしまった場合。
(n-1)個中(k-1)個が別の手紙を受け取っており、新たなn個目が元々別の手紙を受け取っていた(k-1)個の手紙と入れ違ってしまった場合。
(n-1)個中k個が別の手紙を受け取っており、新たなn個目は自分の手紙を受け取る場合

この計算は、メモ化やDPを使うとO(NK)なので、smallなら余裕で通る。
しかしlargeはNが大きすぎるので通らない。

この問題はもう一つ別の解き方がある。
まずN個中自分の手紙を受け取らないK個を選び、かつそのK個内がいずれも自分と異なる手紙を受け取る、と考える。
前者は ${}_NC_K$ = C(N,K)で良い。
後者は、上の関数calcを使うとcalc(K,K)となる。
答えはC(N,K) * calc(K,K)なので、それぞれ求めていく。

先に後者を求める。
上の式から、calc(K,K) = calc(K-1,K-2) + (K-1) * calc(K-1,K-1) + calc(K-1, K)となる。
ここで、calc(K-1,K)は0である。人の数より多い手紙の間違いをすることはない。
また、calc(K-1,K-2)=(K-1)*calc(K-2,K-2)である。(K-1)個のうち１つ自分自身の手紙を受け取るものを選び、残り(K-2)が自分以外の手紙を受け取ればよい。
結局calc(K,K) = (K-1) * (calc(K-2,K-2) + calc(K-1,K-1) )であり、これはO(K)で計算できる。

問題はC(N,K)。最初パスカルの三角形で求めようとしたが、これだとO(NK)で破たんする。
そこで元々の定義に帰ると。 ${}_NC_K = \frac{N!}{K!(N-K)!}$ で、これはO(K)で計算できる。
K!の除算が問題になるが、幸いこの問題はmod 177777777を答える問題なので、1～Kの逆元を求めておけば、除算を使わず処理できる。

s64 N,K;
s64 D[1000000];
s64 mo[1000000];

s64 rev(s64 num) {
	s64 mod=1777777777;
	s64 pw = mod-2;
	s64 ret = 1;
	for(s64 i = 30; i >= 0; i--) {
		ret = (ret*ret)%mod;
		if((pw>>i)&1) ret = (ret*num)%mod;
	}
	return ret;
}
s64 co(s64 n,s64 k) {
	s64 res=1;
	while(k>0) {
		res = (res*(n%1777777777))%1777777777;
		res = (res*mo[k])%1777777777;
		n--;
		k--;
	}
	return res;
}

void solve() {
	s64 res;
	s64 i,j;
	
	scanf("%lld",&N);
	scanf("%lld",&K);
	MINUS(memo);
	
	D[0]=0;
	D[1]=0;
	D[2]=1;
	for(i=3;i<1000000;i++) D[i]=((i-1)*D[i-2] + (i-1)*D[i-1])%1777777777;
	
	mo[1]=1;
	for(i=2;i<=777777;i++) mo[i]=rev(i);
	
	res = co(N,K)*D[K] %1777777777;
	//res = calc(N,K) % 1777777777;
	
	_P("%lld\n",res);
}

合わせるとこんな感じ。
逆元を求める関数は最初拡張ユークリッドの互除法を使おうとしたが、素数に対してはもっと簡単な式があるのでそれを利用した。

まとめ

${}_NC_K$ はパスカルの三角形を使うとO(NK)かかるが、modの縛りがある場合は逆元を使ってO(K)でできることが分かった。
上位の人はとっくにこれ使ってるみたいだな、道理で ${}_NC_K$ で余り迷わないわけだ。
いい勉強になった。

補足：上のcalc(K,K)の話ってWikipediaにあるモンモール数そのまんまだな。まぁ自分で式を導出できたしいいか。
http://ja.wikipedia.org/wiki/%E5%AE%8C%E5%85%A8%E9%A0%86%E5%88%97

kmjp's blog

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

AtCoder ARC #009 : C - 高橋君、24歳

まとめ