跳转至

Y535 幸运666

题目大意

给出正整数 ，问：在包含 \(\overline{666}\) 的自然数中，第 \(k\) (\(k\le 10^{14}\)) 小的数是哪个数？

题解

对于这种求出排名第 \(k\) 的方案，我们可以逐步确定每位的数值。对于第 \(i\) 位，若填 \(a_i\) 能使 \(\overline{a_na_{n-1}\cdots a_{i+1}a_i???\cdots?}\) 可能达到的排名区间 \([l,r]\) 满足 \(k\in[l,r]\)，则该位一定填 \(a_i\)。

要想求出填 \(a_i\) 时的排名区间 \([l,r]\)，可以先预处理出 \(f_{i,[0,3]}\)，其中

  • \(f_{i,0}\) 表示位数为 \(i\)，不存在 \(\overline{666}\)，最高位不是 \(6\) 的方案数；
  • \(f_{i,1}\) 表示位数为 \(i\)，不存在 \(\overline{666}\)，最高位开始只有一个连续的 \(6\) 的方案数；
  • \(f_{i,2}\) 表示位数为 \(i\)，不存在 \(\overline{666}\)，最高位开始有且仅有两个连续的 \(6\) 的方案数；
  • \(f_{i,3}\) 表示位数为 \(i\)，存在至少一个 \(\overline{666}\) 的方案数。

转移如下：

\[ \begin{cases} f_{i,0}=9(f_{i-1,0}+f_{i-1,1}+f_{i-1,2})\\ f_{i,1}=f_{i-1,0}\\ f_{i,2}=f_{i-1,1}\\ f_{i,3}=10f_{i-1,3}+f_{i-1,2} \end{cases} \]

求出 \(f_{i,[0,3]}\) 之后，我们可以直接通过枚举求出答案的位数：

1
2
3
4
int cnt;
for(cnt = 3; cnt < N; cnt++) {
    if(f[cnt][3] >= k) break;
}

接下来，我们逐位考虑。容易发现，对于第 \(1\) 位（最高位），我们可以简单的枚举填的数字：

1
2
3
4
5
6
7
8
9
for(int j = 0; j <= 9; j++) {
    tmp += (j == 6) ? (f[i][2] + f[i][3]) : (f[i][3]);
    if(tmp >= k) {
        cout << j;
        n -= pre;
        break;
    }
    pre = tmp;
}

这样，我们就确定了第一位填的数字 \(a_1\)。对于第 \(2\) 位，如果 \(a_1\ne 6\)，则仍然可以沿用第 \(1\) 位的做法。然而，如果 \(a_1=6\)，第 \(2\) 位就应该考虑 \(a_1\) 和 \(a_2,a_3\) 组成 \(\overline{666}\) 的情况。因此，\(j=6\) 的情况还应额外计算 f[i][1]：

1
2
3
4
5
6
7
8
9
for(int j = 0; j <= 9; j++) {
    tmp += (j == 6) ? (f[i][3] + f[i][2] + f[i][1]) : (f[i][3]);
    if(tmp >= k) {
        cout << j;
        n -= pre;
        break;
    }
    pre = tmp;
}

第 \(3\) 位同理。将三种情况综合起来即：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
for(int j = 0; j <= 9; j++) {
    int six = f[i][3];
    six += (k >= 0) ? (f[i][2]) : 0;
    six += (k >= 1) ? (f[i][1]) : 0;
    six += (k >= 2) ? (f[i][0]) : 0;
    tmp += (j == 6) ? (six) : (f[i][3]);
    if(tmp >= k) {
        cout << j;
        n -= pre;
        if(k < 3) {
            if(j == 6) m++;
            else m = 0;
        }
        break;
    }
    pre = tmp;
}

同时特判已经 \(k=3\) 的情况，直接将 \(n\) 输出到剩余的位中：

1
2
3
4
if(k == 3) {
    cout << ((k - 1) / pw[i] % 10);
    continue;
}

其中 \(-1\) 的原因是，本题从 \(0\) 开始数，排名第 \(k\) 的数是 \(k-1\)。