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箇所に配置できると考える。
基数2は2個ある。で、3箇所に配置可能
これは3人におまんじゅう2個をどう振り分けるか?ということなので、
重複組み合わせで、3-1+2 C 2 = 4 C 2 = 6
基数3は1個ある。で、3箇所に配置可能
これは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; } };