TopCoder SRM 517 - simezi

Easy, Mediumでリサブミットしてしまったものの、highest更新！

173.19 / 180.00 / Unopened
76位 2020 -> 2086

Nという数が書かれたボールを壊すと、それぞれx,yの数字が書かれた二つのボールに分裂する。
ただしここで、x,yはx,y≧2かつxy=Nを満たすような自然数である。

x,yが上の条件を満たすのは解っているが、どのようなx,yになるかは解らない。
壊すボールは自由に選ぶことができるとき、targetの数の書かれたボールを必ず作れるならYESを、
そうでないならNOを出力せよ。

N, target≦100000

あーなんかめっちゃ場合分け面倒そうな問題。これはchallenge回になるだろうという予感。

うーんと、基本的にtargetがNを割り切り、素数ならいい感じ……？
あ、いやそれだとダメなサンプルがある。N=8でtarget=4の場合。

えーと……、あーp^3はどうやってもpとp^2に分かれてしまうのか。
ふむふむ、じゃあtargetが素数か、i*i=targetでi*i*i=Nの場合もOKにすればいいのか？
本当かよ……

うーんとりあえずサンプルは通るようになった。
targetが複数の素因数からなる合成数だとダメなのを一応証明しよう。
N=p1^q1*p2^q2*…… target=r1^s1*r2^s2……と書けるとき、Nがp1^q1と残りに割れたらダメ。以上。

よし。スペルミス等もないよね。よく確認して送信。
送信後また見直す。

……あれ、N=i^4でtarget=i^2の時ってYesじゃねーの……
うわああああああやってしまった。
targtet=i*i, N=i^k (k≧2)は全部Yesだ。

だから最初から嫌な予感したんだ（TT）
再送信。

0,1,2,...,N-1を並び替えた数列が与えられる。

これを、0,1,2,...,N-1という数列から出発して、

……

という操作をどれも必ず一回、しかし順番は自由に適用して作る。
そのような順番は何通りあるか、mod 1000000007で出力せよ。

うぎゃーいかにも苦手そうな組み合わせの問題来た。
そして多分、更に苦手なDP問題。

しばらくサンプルを手で実行しながらあれこれと考える。
うーん、i番目とi+1番目を入れ替えたら、0番目からi番目と、i+1番目からN-1番目は
それぞれ切り離されて、もう要素を移動させることはできない。

えーとだからどうなるんだろ……
それぞれの場合の数を掛け合わせるのかな？
いや違う、階乗か何かになるのか？
最後のでっかいサンプルってn!になってないだろうか。なってないらしい。
じゃあ階乗ではない。

切り離された後って、同じ部分問題に分けられてるよねこれ。
ってことは再帰関数で書けばよくない？
rec(vi v)〜みたいなのを書こうとする。

えーと、考えにくいから、0,1,2,...,N-1という数列から出発するんじゃなくて、
問題の数列から出発して、ソートすると考えよう。
操作を全て逆順にするだけなので場合の数は同じ。

んで、数列のi番目i+1番目を入れ替えると、左側は数列の小さいほうから順にi個の項が（順番は変だけど）ぴったり入っているようなiについて再帰を考えればいい。

んで、再帰書いた。ついでにvectorをメモ化もした。
で、肝心の答えだけど、Σrec(l)*rec(r)にすればいいのかな？
サンプル合わない。。。

んーと、l側ではlの個数-1手の入れ替えが必要。r側ではrの個数-1手の入れ替えが必要。
ってことは、合計する前にC[l+r-2][l-1]倍してやらないとダメだ。

ヤバい時間ない！！
コンビネーションを書く。最後以外サンプル通った！！！
最後マイナスになる……オーバーフローだろう多分。
あ、やっぱりmodとってない箇所がある。mod取る。サンプル合った！送信！！

送信後見直し。
mod取り忘れてる箇所がある。うーん、多分大丈夫な気がするけど、全箇所でmodとらないともしかして失敗したらバカらしい。どうせ2完の中では最下位の順位だから気にせず再送信しよう。
再送信。ちょうど時間が終了する。

あけてない。

部屋の250が一瞬で二つ落とされる。
てか自分と同じ解法の人が全然いなくて凄く不安になる。
みんなDPでやってる。あー、DPでやれば場合分けもクソもないじゃんかーorzみんな頭いい。

てかその割りに自分の解法は落とされていない。
最初の2撃墜以外部屋では撃墜が全く起こらず、チャレンジ終了。
自分の250と500は一回ずつチャレンジされてて、2回とも防衛してた。

どっちも通った！よっしゃあ！！