Project Euler 698 123 Numbers

开启传送门

题目描述

We define 123-numbers as follows:

  • 1 is the smallest 123-number.
  • When written in base 10 the only digits that can be present are “1”, “2” and “3” and if present the number of times they each occur is also a 123-number.

So 2 is a 123-number, since it consists of one digit “2” and 1 is a 123-number. Therefore, 33 is a 123-number as well since it consists of two digits “3” and 2 is a 123-number.
On the other hand, 1111 is not a 123-number, since it contains 4 digits “1” and 4 is not a 123-number.

In ascending order, the first 123-numbers are:
$1,2,3,11,12,13,21,22,23,31,32,33,111,112,113,121,122,123,131,\dots$

Let $F(n)$ be the $n-th$ 123-number. For example $F(4)=11$, $F(10)=31$, $F(40)=1112$, $F(1000)=1223321$ and $F(6000)=2333333333323$.

Find $F(111111111111222333)$. Give your answer modulo $123123123$.

题意

定义一种数字:

  • 1是这种数字
  • 如果一个数字在10进制下只包含1,2,3,并且这些数字出现的次数也是这种数字,那么这个数字也是这种数字。

将这种数字从小到大排序后得到一个序列,问你这个序列的第 $111111111111222333$ 项 % $123123123$。

分析

一个简单的想法是,对于每个固定长度的数字,我们可以得到所有可行的答案数。基于这个想法我们能很快定出答案的长度。

然后现在已经知道答案的长度了,我们可以枚举每一位答案,看当前位应该是几。

然后答案就很明显了。

代码

给大佬递上我奇丑无比的代码 (/ω\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
num = [0,1,2,3,11,12,13,21,22,23,31,32,33,111,112,113,121,122,123,131]
upper = 111111111111222333

def check(a):
for i in range(0, 20):
if num[i] == a:
return True
return False

def fac(a):
if a == 0:
return 1
return a*fac(a-1)

def C(a, b):
return fac(a)/fac(b)/fac(a-b)

def real_get(a, b, c, length):
ret = 0
for i in range(0, 20):
if num[i] > length:
break
if num[i] < a:
continue
for j in range(0, 20):
if num[i] + num[j] > length or length - num[i] - num[j] < c:
break
if num[j] < b or check(length - num[i] - num[j]) == False:
continue
ret = ret + C(length-a-b-c, num[i]-a) * C(length-b-c-num[i], num[j]-b)
return ret

def equal(a, b):
if a==b:
return 1
return 0

index = 0

for index in range(1,50):
buf = real_get(0,0,0,index)
if upper >= buf:
upper = upper - buf
else:
print index, upper
break
a = [0, 0, 0]
ans = 0
for i in range(0, index):
for j in range(0, 3):
buf = real_get(a[0] + equal(j, 0), a[1] + equal(j, 1), a[2] + equal(j, 2), index)
if upper > buf:
upper = upper - buf
else:
a[j] = a[j] + 1
ans = ans * 10 + j + 1
break
print ans % 123123123