1. 問題
 基底Nの整数がビューティフル(Beautiful)というのは、0~N-1の数値がすべて使われ、隣り合う桁の数値の差が1ということ。例えば、9876543210は基底10でのビューティフルナンバーだ。
 基底N (2<=N<=10) と桁数M (0<=M<=100) が与えられた時、M桁以下のすべてのビューティフルナンバーの総数を示せ。

2. いくつかの実例
 N=2, M=4に対するビューティフルナンバーは、10, 101, 1010の3つ。
 N=3, M=7に対しては、210, 2101, 21010, 21012, 210101, 210121, 2101010, 2101012, 2101210, 2101212, 21210, 212101, 2121010, 2121012, 2121210, 101012,1010121,1012, 10121, 101210, 1012101, 101212, 1012121, 1210, 12101, 121010, 1210101, 121012, 1210121, 121210, 1212101の31個がビューティフルナンバーだ。
 N=10, M=10に対するビューティフルナンバーは 9876543210の1つ。

3. 計算方法
 ここでは、DPによる方法を考える。
 m桁目に数値nである数字の数は a[m][n][b](大きさはa[101][10][1024])とする。bは1~m桁までの各数値に対応するビットパターン。1<=m<=100, 0<=n<10, 0<b<=1024。

  a[m+1][n][b|bp[n]] = a[m][n+1][b] + a[m][n-1][b]

  bp[10] = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 };
  初期値 a[1][n][bp[n]] = 1 for 1<=n<10

基底がN, 桁数がちょうどMのビューティフルナンバーの数を c[M][N] とすると、

p11472.jpg

  full[11] = { 0, 0, 3, 7, 15, 31, 63, 127, 255, 511, 1023 };

最終的に、問題の解答を得る。

    scanf("231314736-2082935264", &N, &M);
if (M < N) puts("0");
else if (M == N) puts("1");
else if (N == 2) printf("231314736\n", M-1);
else {
int ans = 0;
for (m = 1; m <= M; m++) ans = (ans + c[m][N]) % 1000000007;
printf("231314736\n", ans);
}

4. 検証用入出力データ

18
2 50
3 50
4 50
5 50
6 50
7 50
8 50
9 50
10 50
2 100
3 100
4 100
5 100
6 100
7 100
8 100
9 100
10 100
49
167772006
181208395
203197534
856300377
756922568
423236469
509230823
322172256
99
494806323
187470286
778091614
151286785
265624146
626153492
829010450
958872830

5. 感想
 わりと正解率の高い問題だが、自分ではそれなりに考えた。もっと簡潔な解き方があるかもしれない。

Comments are closed.

Post Navigation