No.741 AscNumber(Easy)
はじめに
競技プログラミング、yukicoder
No.741 AscNumber(Easy)
言語はC#
何かあればTwitter→@pirorirori_n712まで
問題
入力
N 1<=N<=1000000
出力
10^N未満のAscNumberの個数を10^9 + 7で割った余り
AscNumberの定義
非負整数のうち、10進数表示をしたときに桁が昇順に並んでいるもの 例えば、0,1,9,123,1359,12234,55555はAscNumberです。21,132,3141,2590,43221はAscNumberではありません。
☆解き方
10N未満の数にはいくつAscNumberが含まれているか
まず、10N未満の数にいくつAscNumberが含まれているかを考える。
AscNumberの定義は上の通り、桁が昇順に並んでいるものである。
そのため、一見これは並び替えの問題に見える、
が組み合わせにして考えるとやりやすい問題である。
（並び替えでもできるのかもしれませんが、私は方法を発見できていないです）
考えからは複数あると思われるが、私は以下の考え方で腑に落ちました。
10N未満の数を作成するとき、
使える数字は「0～9の10個」、桁数は「1～N」です。
これを以下のようにして、10N未満の数を作成します。
①0～9までの数字が書かれた箱を用意します。→これが使える数字
②次にN個のボールを用意します。→これが桁数
③箱の中にボールを適当に入れます（箱に書かれている数字は、全く気にしない）
そうすると、
箱の両側は仕切りと考えられるので
真横に「11個の仕切り」と「N個のボール」が並ぶことになります。
つまり、これは「11個の仕切り」と「N個のボール」の
重複を許す組み合わせの問題だと言えます。
下の図は
Nを5として、適当に5個のたまを
箱にいれてみた場合の並びのイメージです。
ここでは
左から順に仕切りをa,ボールをbとすると以下のように並んでいます。
「aabaaabbaaabaaba」
またここではボールが
「1の箱に1つ」「4の箱に2つ」「7の箱に一つ」「9の箱に一つ」
入っているので出来上がる数字は「14479」です。
この考え方でポイントとなるのは、
ボールが入った箱の数字は「一つの桁の数字」なので、
並び替えではなく組み合わせとして考えるということです。
式を組み立てる
後は重複を許す組み合わせの問題なので
Conbinationを使って式を組み立てていきます。
まず、ボールの数は
横に並ぶ数字の数（桁数）なので「N」個
そして仕切りの数は
「0～9」の数を表す（0～9の箱（の仕切り）を用意する）ので「11」個です。
この「N」と「11」を組み合わせにします。
まず、仕切りは「0～9」の箱の仕切りです。
箱である以上、左端と右端は必ず仕切りがくることになります。
つまり、一番左と一番右は仕切りで固定します。
そうすると、
中身の「(11-2=9)個の仕切り」と「N個のボール」の
並び替えをすればいいことになります。
そうすると、式は重複を許す組み合わせなので
コンビネーションを使って
(9+N)C9
となります。
参考：
重複組合せについて（３Ｈ文系数学）
重複組み合わせは絵を描けば理解できる。イラストで解説
107+9で余りを出すタイミングはいつか
ここまで、
10N未満の数でAscNumberがいくつあるかを考えてきましたが
この問題の出力はAscNumberの個数を
「107+9」で割った余りです。
分母を全てかけてしまってから、
或いは、分母をかけてかつ分母で割ってAscNumberの数を正確に出してから
最後に割って余りを計算するということは、
途中で数が大きくなりすぎてしまうのでできません。
そのため、AscNumberを全て求め切らないうちに
「107+9」で割りながら処理を進めていく必要があります。
まず先ほどのコンビネーションの式を
解ける形に分解すると、以下のようになります。
(9+N)*(9+N-1)…(9+N-8)/9*8…1
これを見ると、
割り算（÷(9×8…1)の部分）をしながら
「107+9」で割って余りを求めなければならないことが分かります。
この割るタイミングですが、
私自身よく分かっていないので
書けないのですが、何回かWAをとるうちに
余りを求めてから割っても、答えが合わないということに気づきました。
そのため、「107+9」で割る前に「9×8…1」で割っています。
（実際は逆元をかけるということをするらしいです、mod理解したい…
「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜）
分母の割り算で気をつけること
分母の割り算とは「÷(9×8…1)」の部分です。
ここで気を付けなくてはならないことは、
「割り切れるときに割らなければいけない」ということです。
例えば、分子が100であるときに分母が9だった場合
これは割り切れずに余りが出てしまいます。
「割り切れるときに割る」とは、
こういった余りが出る場面を避けて
余りが0になるとき（或いは、分母を分解したもので分子を割って割り切れるとき）に
分子を分母で割るということです。
実際のコードでは
分母は常に「÷(9×8…1)」であることから
それぞれの数字を最小の単位に分解して（例：9→3**3なので3,3）リストに入れ、
割ったらリストから除くということを行いました。
コード例
using System;
using System.Linq;
using System.Collections.Generic;
class No741
{
static void Main()
{
//入力に9を足して、すぐに組み合わせの式の分子に使えるようにしておく
//N+9→分子の掛け算のスタートとなる数字
var n = long.Parse(Console.ReadLine())+9;
//リストに分母の数字を分解したものを入れる
//9!→9*8*7…1→分母
//ここでは前から順に分解して入れています
//1は割っても変わらないので省いて2～
var list = new List<long> { 2, 3, 2, 2, 5, 2, 3, 7, 2, 2, 2, 3, 3};
//答えの変数を用意
//掛け算して数を変えていきたいので1を代入
long ans = 1;
//分子のかける数ぶん回します
//N+9*(N+9-1)*(N+9-2)…(N+9-8)
for (long i = 0; i < 9; i++)
{
//一回回すごとに(N-9)から1ずつ引いた数をかける
ans = ans * (n - i);
//分母の割り算
//現在リストに入っている数ぶん回します
//順番や一度に割る数は関係ないので、割れるときにできるだけ多く割っておきます
for (int j=0;j<l.Count;)
{
//もしリスト内の数字で割ったときにあまりがなかったら
if (ans % l[j] == 0)
{
//確実に割り切れる数字で分母を割ります
ans /= l[j];
//割った数字はもう使わないのでリストから削除します
l.RemoveAt(j);
}
//リストから数字を削除した場合は
//次の数字のインデックスは今の数字のインデックスのままですが
//（リストから削除すると勝手に詰めてくれるので）
//割らなかった場合は次の数字に進めるためにインデックスを1進めます
else j++;
}
//分母の数で割った後に10^7+9で割って余りをansに入れます
ans %= 1000000007;
}
//答えを出力します
Console.WriteLine(ans);
}
}
