SRM565 Div2 Hard "DivisibleSequence"

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12274

訳

N から始まり、長さが H の divisible sequenceとは、
下記のような性質を持った正の整数の配列である。

・その配列はA[0]～A[H-1]のH個の要素を持っている。
・A[0]の値は N である。
・A[i+1]はA[i]の約数である。( 0 <= i <= H-2 )

N と H が与えられる。
Nから始まり、長さHのdivisible sequenceが何パターンできるかを返せ。

制約

1 <= N <= 10^9
1 <= H <= 10^9

考えた事

Hが10^9かよ・・・
まさか累乗行列？

でもNも10^9ででかいから、
行列の要素数がヤバイことになるな・・

うーんうーん・・・

～～（一時間後）～～

"srm 565 hard 解法"(ｶﾀｶﾀｶﾀ ﾀｰｰｰﾝ!!!
検索 (ｶﾁｯ

なるほろ・・・
Nを素因数分解して、前の数値を割るときに、
各基数を何個使うのか？ってことになるわけか・・・

例えばN=12 H=3であれば、
12 = 2^2 * 3^1
割るタイミングは２回で２箇所に基数を配置できる
でも基数は使い切らなくてもいいから３箇所に配置できると考える。

基数2は2個ある。で、３箇所に配置可能
これは３人におまんじゅう２個をどう振り分けるか？ということなので、
重複組み合わせで、3-1+2 C 2 = 4 C 2 = 6

基数3は1個ある。で、３箇所に配置可能
これは３人におまんじゅう１個をどう振り分けるか？ということなので、
重複組み合わせで、3-1+1 C 2 = 3 C 2 = 3

よってパターン数は6 * 3で18になる！

ソースコード

const int MOD = 1000000009;

// 各指数のコンビネーション
long long C[50];
// 各基数の指数
int P[32000];

class DivisibleSequence {
public:

    long long pow_mod( long long x, int n ){
        long long a = 1;
        while( n > 0 ){
            if( (n & 1) == 1 ) a = a * x % MOD;
            x = x * x % MOD;
            n >>= 1;
        }
        return a;
    }

    long long inv_mod( long long a ){
        return pow_mod( a, MOD - 2 );
    }

    int count(int N, int H){

        // Cを初期化
        C[0] = 1;
        for( int p = 1; p <= 32; p++ ){
            C[p] = C[p-1] * (H + p - 1) % MOD * inv_mod( p ) % MOD;
        }

        // 各基数の指数を取得
        int max_d = (int)sqrt((double)( N ));
        memset( P, 0, sizeof(P) );
        for( int d = 2; d <= max_d; d++ ){
            while( N % d == 0 ){
                P[d]++;
                N /= d;
            }
        }
        if( N != 1 ) P[0]++;

        // 掛け合わせて行く
        long long res = 1;
        for( int i = 0; i <= max_d; i++ ){
            res = res * C[P[i]] % MOD;
        }

        return (int)res;
    }
};