Hatena::Grouptopcoder

解いた問題

TopCoder: OgieKako / Codeforces: OgieKako

 | 

2012-01-09

SRM502 1000

11:02

N,K が与えられる.

{0,1,...,N-1} から K 個 選んで,和がNで割り切れるようにする方法の数 を mod 1e9+7 で求めよ.

N <= 1e9

K <= 1000

----------

集合の数を求めようとすると,それは昇順の列の数に対応していて,昇順という制約は(Nがでかいから)厄介なので,

順序を気にしない,すべての要素が異なる,列の数 を求めることにして,あとでK ! で割る.


a_1,..., a_{K-1} まで決めたら, 和を0 にする a_K は一意に定まる.

a_i = a_K とならないパターンの数を求めたい.

A : a_1...,a_{K-1} をすべて異なるようにする方法の数

とすると, これは, N * (N-1) * ... * (N-(K-1)+1) 通り.

B : a_1,...,a_{K-1} が全て異なり,そのいずれかが,a_K と一致する組み合わせの数

とすると,

A-B が 解となる.

B' : a_1 + ... + 2 * a_{K-1} = 0 (mod N) (a_i はすべて異なる)

とすると, B = (K-1) * B'.


改めて,

f(K,d) : a_1 + ... + d * a_K = 0 (mod N) (a_i はすべて異なる) なる組み合わせ

と置く.

d の mod N での軌道は, {gcd(d,N) の倍数}. この位数は N/gcd(d,N).

よって,a_1 + ... + a_{K-1} が gcd(d,N) の倍数でないと, 解を持たない.

逆に,倍数のとき,a_K は gcd(d,N) 個の解をもつ.

よって,

A : a_1 + ... + a_{K-1} がすべて異なり,gcd(d,N) の倍数 なる組み合わせ

B : a_1 + ... + a_{K-1} がすべて異なり,(gcd(d,N) の倍数 *1 ), そのどれかがa_K と一致する

とすると,

A * gcd(d,N) - B が解となる.

B' : a_1 + ... + (d+1) * a_{K-1} = 0 (mod N)

とすると, B = (K-1) * B'.


改めて,

f(K,d,m) : a_1 + ... + d * a_K = 0 (mod m) (a_i はすべて異なる) なる組み合わせ

と置く.

d の mod m での軌道は,{gcd(d,m) の倍数}. この位数は m/gcd(d,m).

よって,a_1 + ... + a_{K-1} が gcd(d,m) の倍数でないと,解を持たない.

逆に,倍数のとき,a_K は N/(m/gcd(d,m)) 個の解を持つ.

よって,

A : a_1 + ... + a_{K-1} がすべて異なり,gcd(d,m) の倍数 なる組み合わせ

B : a_1 + ... + a_{K-1} がすべて異なり,(gcd(d,m) の倍数((後の条件よりこれは必ず満たされる))), そのどれかがa_K と一致する

とすると,

A * N/(m/gcd(d,m)) - B が解となる.

B' : a_1 + ... + (d+1) * a_{K-1} = 0 (mod m)

とすると, B = (K-1) * B'.



以上より,

f(K,d,m) = f(K-1,1,gcd(d,m)) * N/(m/gcd(d,m)) - f(K-1,d+1,m) * (K-1).

基底部は, f(1,d,m) = N/(m/gcd(d,m)). (f(0,d,m) = 1 でもよい)


この漸化式をそのまま使うと,メモ化してもTLE する.

K,d はたかだか 与えられたK までで, m は Nの約数を動く.約数の個数は O(sqrt(N))だが,

m は gcd(d,m) として生成され,dはたかだかK なので,m もNでなければK以下.

状態数は,O(K * K * K) であり,定数倍が小さそうだが,やってみると,間に合わない. 3倍くらい高速化すれば通りそうに思える.


高速化を考えよう. 関数の先頭で d%=m としてよい. これによって,常に d<m となり, 状態数は, O( sum(Nの約数でK以下のもの) * K ) となる.</ppp>

実は,もっと状態数は小さく,O( NのK以下の約数の数 * K) となっている.

f(K-1,1,gcd(d,m)) と書いてあると気づきにくいが,これは

f(K-1,d+1,gcd(d,m)) と等しい. 2番目の式は f(K-1,d+1,m) であるので,つまり,

d の値は,常に (与えられたK)+1 - K (mod m) に等しいのである.

よって上記のオーダーを得る.


----------

さらに高速化:


a_1 + ... + a_K = 0 (mod m) とすると, 各a_i に 1 を足すと, 和が K (mod m) になる.

これを繰り返すと, K の軌道は {gcd(m,K) の倍数} なので, m/gcd(m,K) 回でもとに戻る.

よって,

f(K,1,m) = f(K,d,gcd(m,K)) / (m/gcd(m,K))

である.

初めににこうすることにより,上に述べた理由で, d%=mの高速化を入れないと,

O(K * K * sqrt(K) ) となる. これでは間に合わなかった.


d%=m の高速化を入れると,同様にして,状態数 O(Kの約数の数 * K) = O( sqrt(K) * K ) を得る.

*1: 後の条件よりこれは必ず満たされる

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/ogiekako/20120109
 |