SRM252 DIV2 500pts

ニコニコ生放送で診断人さんがTopcoderの問題を解いていたのでwktkしながら視聴してました。


We define a permutation of an integer n as an integer that has the same digits as n, but in an arbitrary order. Two permutations of n are considered different if the numbers they represent are not the same. For instance, the set of all possible permutations of the number n = 313 is: {133, 313, 331}. Given an int n, your task is to find the sum of all its permutations.
Examples
0)
157
Returns: 2886
We have: 157 + 175 + 517 + 571 + 715 + 751 = 2886
1)
313
Returns: 777
We have: 133 + 313 + 331 = 777
2)
1234
Returns: 66660

解法も説明してたので自分もそれに沿って実装を試みたのだけど、ものすごく躓きました。


解法１
157 + 175 + 517 + 715 + 751 = 111 + 111 + 555 + 555 + 777 + 777 = 2886
133 + 313 + 331 = 111 + 333 + 333 = 777
足し算だから、それぞれの同じ桁の値を入れ替えても結果は同じであることに注目して
111 + 111 + 555 + 555 + 777 + 777 = 111 * ( 1+1 + 5+5+5 + 7+7+7 ) = 2886
111 + 333 + 333 = 111 * ( 1 + 3+3 ) = 777


( 桁数分の11...n ) * ( (値xを固定したときの順列パターン数 * x) + ... 出現した値の種類の個数 )


値ｘを固定したとき、残りの桁数をｎ、使用されてない値の個数をｍ
{n}C{m1} * {n-m1}C{m2} * {n-m1-m2}C{m3} ... 値ｘを1つ除いた残りの重複しない値の個数-1回分
これで値ｘを固定したときのパターン数を得られる。


解法２
C++さーん、出番ですよー。
STLの　next_permutation()　を使えば全ての順列を生成してくれるというスグレモノ。
生成→足し算→おわり

当然、実行結果を比較すると、後者のほうが遅い。Topcoderだと解法2はTLEになるのかもしれない。
Topcoderの問題を掲載したわけだけど…、Topcoderやったことない＼(＾o＾)／
英語が出来ないのってほんと壁だよねｗ