ABC110D - Factorization
今回の提出は、他人のライブラリーから関数をパクってきたので、以下のコードは謎の関数名があります。
他人のライブラリーから書いたコードを自分のブログに書くのは気が引けるので、
気になる人は某んちょんさんのブログとか、nCmの求め方。みたいなのを自分で調べてください。
ちなみに僕は某んちょんさんのブログから借りました。
int main() { cout << setprecision(10); cin >> n >> m; vector<pair<ll,ll>> fact; fact = factorization(m); ll ans = 1; COMinit(); for(auto x : fact){ ll k; k = x.second; //n人にk個の因数を分ける。物はk+n-1、仕切りはn-1 ans *= COM(k+n-1,n-1); //COM(k+n-1,n-1) は、 (k+n-1) C (n-1) を1e+7の余りを求めながら頑張って求めてくれる ans %= mod; } cout << ans << endl; }
解法
青ディフィカルティの問題
解けた。嬉しすぎる。
数列をn個に分けて、その数列の要素の積がmになるようにする。
多分、大半の方が素因数分解すればよさそうだな。ってことは分かると思う。
ではまあ、 m = 12 = 2 * 2 * 3 と素因数分解できたとしよう。
ここで、n = 3 であるとする(サンプルケースと同じ例)
つまり、求める数列の数2,2,3を3つに分けるとき、その分け方が何通りになるかということが聞かれている(と思う)
m の素因数である二つの2と一つの3をどのように分けるか考える。
n = 3であるとき、もうめんどくさいから A 君 B君、C君の3人に分けると考えよう。
例えば、A君に2を二つ上げると、A君は貰った値の積の4を持っている
B君に3を一つ上げると、もらった値の積(?)3を持っている
C君はなんももらっていない。このときは1を持っているとする。
こういう風に分けると、ちゃんと数列の要素(3人の持ち物)の積は12になっている。
求める組み合わせの数は、2の分け方C2通り* 3の分け方C3通りである。
・同じ因数が2つ以上ある場合を考えるのは少し厄介(この場合は因数2のこと)
・因数が一つなら簡単(この場合は因数3について)
まず後者について、3をA~Cの3人の中で誰に上げるかを考えるので3通り。
次に前者を考える。
2つの因数2を3人に分ける。
A~C君は、2を貰う個数は0個でもいいが、3人が貰った2の個数の合計が2("2つ"の2)である必要がある。
A君、B君、C君が貰う2の個数をそれぞれa , b , cとすると
a + b + c = 2 (a , b, c >= 0)
というような条件になる。以下は僕がマスターオブ場合の数で学んだこと以下を存分に使って解説をしてやろう!!!(受験を経験した人なら多分既に知っているかも。僕は忘れていた)
まずは、 x+y+z=5 (x , y, z >=1 )を考えてよう。
次に a + b + c = 2 (a , b, c >= 0) を考えよう
画像4枚貼ったよ!!(見れるかな…)
でつまり、結果をいうと
a + b + c = 2 ( a, b , c >= 0) の解が何通りあるかっていうと、
(2 + 3 - 1 ) C ( 3 - 1 ) = 4 C 2 通りなのです!!
よって、2つの因数2の分け方は6(= 4C2)通り
1つの因数3の分け方は3通り。
因数2のわけかた、因数3の分け方を掛け算した18が答え!!(これはサンプルの答えと一致しているね)
でまぁ、mの因数の種類がk通りあって、 a1, a2, ... ak,みたいな感じになってたとしたら
k種類のai (i<=k) について、n人に分ける方法が何通りあるかを考えて、それを掛け算すればいいのだ!!!!
でも…
n C m の計算とか 1000000007 で割った余りを求めるの大変だよね…
僕は分からなかったから n C m 求め方 c++ みたいな感じで調べて某んちょんさんが書いてたコードをそのまま使ってACしたよ!!!
この辺は僕は説明できないからここで終わり!!ばいばーい