Hatena::Grouptopcoder

解いた問題

TopCoder: OgieKako / Codeforces: OgieKako

 | 

2013-02-07

SRM569 Hard - MegaFactorial

03:23

問題

n!0 = n
0!k = 1
n!k = n!k-1 * n-1!k ... (1)
とする. n!k をB進数表記した時の末尾の0の個数をmod 1e9+9 で求めよ.
n<=1e9, k<=16, 2<=B<=10.

解法

立式

n!k に,1<=m<=n の寄与がいくつあるかを考える.

n方向,k方向の二次元の格子を考えると,

(m,1) から,(n,k) に(最短距離で)到達する方法の数の分だけ寄与することが,(1)よりわかる.

すなわち,{n-m+k-1 \choose k-1} の寄与がある.

よって,

n!k = \prod_{1\leq m\leq n}m^{n-m+k-1\choose k-1}.

B<=10のおかげで,ある素数pに対して上式が何回pで割れるかをmod M (M = 1e9+9 or 2 or 3)で計算出来れば解が求まる(詳細は略). その値は

 \sum_j\sum_{1\leq ap^j\leq n}{n-ap^j+k-1\choose k-1}.

P = p^j はすべて回すことにして,m = floor(n/P) と置くと,

 \sum_{1\leq aP\leq n}{n-aP+k-1\choose k-1} = \sum_{0\leq a\lt m}{n-mP+aP+k-1\choose k-1}

を求めれば良い.

f(N,P,m,K) = \sum_{0\leq a\lt m}{N+aP\choose K}

なる関数を高速に計算出来れば良いことになる.

Kが小さい時の組合せ

まず,単に {N\choose K} を求める方法を復習しておく.

 \begin{array}{C} {n\choose0}\\ {n\choose 1}\\ \vdots \\ {n\choose k} \end{array} = \left(\begin{array}{CCCCC}1&&&& \\ 1&1&&& \\ &&\ddots&& \\ &&&1& \\&&&1&1 \end{array} \right)^n \begin{array}{C}{0\choose 0}\\ {0\choose 1} \\ \vdots \\ {0\choose k} \end{array}

が成り立つ.これは組合せの漸化式からすぐ出てくる.中央の k+1 * k+1 行列をAとおき,右辺のベクトル(先頭要素のみが1)をxとおくと,

 {N\choose K} = \left(A^Nx\right) \[K\].

fを求める

 f = \sum_{0\leq a\lt m}{N+aP\choose K} = \sum_{0\leq a\lt m}{A^{N+aP}x\[K\]} = (A^N(\sum_{0\leq a\lt m}(A^P)^a)x)\[K\].

よって,B=A^Pとしたとき,

 \sum_{0\leq a\lt m}B^a を高速に計算出来れば良いことになる.

これは可能で,

 B' = \left(\begin{array}{CC}B&I \\ 0&I \end{array}\right) とおくと, B'^m の右上にそれが現れる.

あるいは,

 \sum_{0\leq a\lt m}B^ax を直接計算することもでき,

 B' = \left(\begin{array}{CC}B&x \\ 0&1 \end{array}\right) とおくと, B'^m の右上にそれが現れる.こちらのほうが8倍くらい高速.

計算量は,O(\log^2nK^3)くらい.

おわり

ところで,しばらくmodの値を1e9+7と間違えてハマっていたorz

ゲスト



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