競プロ典型90問 005 Restricted Digits（★7）
★7の最高難度の問題がやっとこさ出来たので解説を書く。
問題概要
与えられた数字のみを使ってN桁の正の整数を作る。そのうちBの倍数は何個か。
答えを10^9+7で割った余ってから出力する。
問題の把握
問題が 「1, 4, 9を使って2桁を作る時、7の倍数はいくつか」なら
11, 14, 19, 41, 44, 49, 91, 94, 99
の中で7の倍数を数えればよい。14, 49, 91 の3つが7の倍数なので答えは3。
基本的な解法
x桁使った時の数を余りごとに
- 余り0がa個
- 余り1がb個
- 余り2がc個
のようにメモしておくやり方が基本。次のようにする。
- 1桁使った時の余りを求める
- それにもう1桁追加して2桁使った時の余りを求める
- それにもう1桁追加して3桁使った時の余りを求める
ところがこの問題で与えられる桁数は10^18桁なので上のやり方では時間がオーバーする。
効率的解法の概要
解法の名前がわからんので「効率的解法」と呼ぶ。
大きく2に分けたものを組み合わせるやり方をする。たとえば、
- 7の余り
- 使える数字は 1, 4, 9
- 7桁
のとき、7桁を上の3桁と下の4桁に分ける。
すでに3桁使ったときの余りデータと4桁使ったときの余りデータがあるとする。これを使って7桁の余りデータを作る。
余りデータとは、余りaがx個、余りbがy個…というもの。
余りの組み合わせからひとつ取り上げる。3桁の 449(余り1)と4桁の1949(余り3)から4491949の余りを求める。4491949は
4491949 = 449 * 10000 + 1949
なので10000の余りがわかればいい。これは4。4491949の余りを求めるのに必要なデータは揃った。
- 449(余り1)
- 1949(余り3)
- 10000(余り4)
この3つのデータから(1 * 4 + 3) % 7 = 0となるので4491949は余り0となる。
効率的解法では、このように大きく分けた2つを組み合わせるやり方をする。
例えば、全体を10個に分けてそのうち2つを組み合わせて9個にし、また2つを組み合わせて8個…とする。
その分解の仕方だが効率のよい分解は
1桁、2桁、4桁、8桁、16桁…
となる。例えば7桁なら
7 = 4 + 2 + 1
152桁は
152 = 128 + 16 + 8
の組み合わせになる。2のべき乗にするとどんな数にも対応できる（問題の範囲内で）。
効率的解法の必要なデータ
必要なデータは
- シフトデータ（2つのデータを組み合わせるときに片方をシフトするために必要。上の例では「1000の余りが4」というデータ）
- 2のべき乗桁の余りデータ
となる。2のべき乗桁の余りデータのうち必要なものをシフトさせながら組み合わせる。
ではデータの詳細。
シフトデータ
2つの余りデータを組み合わせる時に使う。シフトデータは
- 1桁シフト用に10を7で割った余り
- 2桁シフト用に100を7で割った余り
- 4桁シフト用に10000を7で割った余り
- 8桁シフト用に100000000を7で割った余り
- つづく
と用意すればよい。100000000を7で割った余りは10000を7で割った余りを2乗する方法で求める。
2のべき乗桁の余りデータ
1, 4, 9の3つを使って
- 1桁を作る時の余りデータ
- 2桁を作る時の余りデータ
- 4桁を作る時の余りデータ
- 8桁を作る時の余りデータ
- つづく
を作成する。8桁の余りデータは、4桁の余りデータを2つ用意して片方を4桁シフトする。
効率的解法の中心処理
準備が出来たので計算する。小さい方から処理する。
与えられた桁が7なら
7 = 4 + 2 + 1
なので
- 1桁のデータを作成
- 2桁を足して3桁のデータを作成
- 4桁を足して7桁のデータを作成
となる。
152桁の
152 = 128 + 16 + 8
なら
- 1桁から4桁は無視
- 8桁のデータを作成
- 16桁を足して24桁のデータを作成
- 32桁と64桁は無視
- 128桁を足して152桁のデータを作成
となる。
もうちょっと具体的に書く。
ポイントは「0桁なら余り0が1個」という状態から出発すること。
例として11桁を求める。
- 「0桁なら余り0が1個」の状態を作って現在のデータとする
- 1桁のデータを追加する。これは既存のデータを1つ左にシフトしてから1桁のデータを追加する。
- 2桁のデータを追加する。これは既存のデータを2つ左にシフトしてから2桁のデータを追加する。
- 4桁のデータは追加しない
- 8桁のデータを追加する。これは既存のデータを8つ左にシフトしてから8桁のデータを追加する。
以上で説明は終わり。
シフトデータ何を使うか
この問題の難しさのひとつが各段階で「シフトデータ何を使うか」で、
- x桁使ったときの余りデータの作成
- 答に向かって情報を追加する過程で、x桁を追加する時
この2つは使うシフトデータがずれています。
x桁使った時の余りデータの作成ではx/2桁を2つ組み合わせてx桁を作るのでx/2桁のシフトデータを使う。
最後の、答を得る工程でx桁を追加する時は、それまでのものをx桁シフトしてからx桁の情報を入れるのでx桁のシフトデータを使う。
以上で小課題3の説明は終わりだが、小課題2について少し補足する。
小課題2について
小課題2のC++の模範解答の行列Aは後ろから適用させるものになっている。
Xの中のある余りの情報(赤丸)が、行列内で影響を与えるのは横方向。
for (int i = 0; i < B; i++) {
for (int j = 1; j <= K; j++) {
int nex = (i * 10 + C[j]) % B;
A.x[i][nex] += 1;
}
}
行列内の横方向の位置nexは、Xの中のある余りの情報(i)に10倍して各Cを足した値。
Discussion