草体にぼ日記

だらだらと

ABC110 D- Factorization

ABC110D - Factorization

提出AC

問題

今回の提出は、他人のライブラリーから関数をパクってきたので、以下のコードは謎の関数名があります。

他人のライブラリーから書いたコードを自分のブログに書くのは気が引けるので、

気になる人は某んちょんさんのブログとか、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 )を考えてよう。 f:id:niboshi_bisyoujo:20191130170117j:plain

次に a + b + c = 2 (a , b, c >= 0) を考えよう

f:id:niboshi_bisyoujo:20191130170215j:plain

f:id:niboshi_bisyoujo:20191130170224j:plain f:id:niboshi_bisyoujo:20191130170232j:plain 画像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したよ!!!

この辺は僕は説明できないからここで終わり!!ばいばーい