题目描述

某次测验后，顿顿老师在黑板上留下了一串数字 $23333$ 便飘然而去。

凝望着这个神秘数字，小 $\textsf {P}$ 同学不禁陷入了沉思……

已知某次测验包含 $n$ 道单项选择题，其中第 $i$ 题（$1 \le i \le n$）有 $a _ i$ 个选项，正确选项为 $b _ i$，满足 $a _ i \ge 2$ 且 $0 \le b _ i < a _ i$。

比如说，$a _ i = 4$ 表示第 $i$ 题有 $4$ 个选项，此时正确选项 $b _ i$ 的取值一定是 $0$、$1$、$2$、$3$ 其中之一。

顿顿老师设计了如下方式对正确答案进行编码，使得仅用一个整数 $m$ 便可表示 $b _ 1, b _ 2, \ldots, b _ n$。

首先定义一个辅助数组 $c _ i$，表示数组 $a _ i$ 的前缀乘积。

当 $1 \le i \le n$ 时，满足：
$$ c _ i = a _ 1 \times a _ 2 \times \cdots \times a _ i $$
特别地，定义 $c _ 0 = 1$。

于是 $m$ 便可按照如下公式算出：
$$ \begin {split} m & = \sum \limits _ {i = 1} ^ n c _ {i − 1} \times b _ i \\\ & = c _ 0 \times b _ 1 + c _ 1 \times b _ 2 + \cdots + c _ n − 1 \times b _ n \end {split} $$
易知，$0 \le m < c _ n$，最小值和最大值分别当 $b _ i$ 全部为 $0$ 和 $b _ i = a _ i − 1$ 时取得。

试帮助小 $\textsf {P}$ 同学，把测验的正确答案 $b _ 1, b _ 2, \ldots, b _ n$* 从顿顿老师留下的神秘整数 $m$ 中恢复出来。

输入格式

输入共两行。

第一行包含用空格分隔的两个整数 $n$ 和 $m$，分别表示题目数量和顿顿老师的神秘数字。

第二行包含用空格分隔的 $n$ 个整数 $a _ 1, a _ 2, \ldots, a _ n$，依次表示每道选择题的选项数目。

输出格式

输出仅一行，包含用空格分隔的 $n$ 个整数 $b _ 1, b _ 2, \ldots, b _ n$，依次表示每道选择题的正确选项。

数据范围

$50 \%$ 的测试数据满足：$a _ i$ 全部等于 $2$，即每道题均只有两个选项，此时 $c _ i = 2 ^ i$；
全部的测试数据满足：$1 \le n \le 20$，$a _ i \ge 2$ 且 $c _ n \le 10 ^ 9$（根据题目描述中的定义 $c _ n$表示全部 $a _ i$ 的乘积）。

输入样例1：

15 32767
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

输出样例1：

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

输入样例2：

4 0
2 3 2 5

输出样例2：

0 0 0 0

输入样例3：

7 23333
3 5 20 10 4 3 10

输出样例3：

2 2 15 7 3 1 0

样例3解释

提示

对任意的 $1 \le j \le n$，因为 $c _ {j + 1}, c _ {j + 2}, \ldots$ 均为 $c _ j$ 的倍数，所以 $m$ 除以 $c _ j$ 的余数具有如下性质：
$$ m \bmod c _ j = \sum \limits _ {j = 1} ^ i c _ {i − 1} \times b _ i $$
其中 $\bmod$ 表示取余运算。

令 $j$ 取不同的值，则有如下等式：
$$ \begin {split} m \bmod c _ 1 & = c _ 0 \times b _ 1 \\\ m \bmod c _ 2 & = c _ 0 \times b _ 1 + c _ 1 \times b _ 2 \\\ m \bmod c _ 3 & = c _ 0 \times b _ 1 + c _ 1 \times b _ 2 + c _ 2 \times b _ 3 \\\ & \ldots \end {split} $$

解题思路

由于题目太长了（长得我打题面的 $\text {Markdown}$ 都用了 $20$ 分钟），我们不妨来简化一下题面：

形式化题意

给你两个数 $n, m$，及 $n$ 个整数 $a _ i$，让你求 $n$ 个整数 $b _ i$，使得 $\sum \limits _ {i = 1} ^ n \left (b _ i \times \prod \limits _ {j = 1} ^ {i - 1} a _ i \right ) = m$（加一对大括号看得更清楚）。

其实 $m$ 可以看成是一个不定进制的数，从右往左数第 $i$ 位是 $a _ i$ 进制。这道题就是给我们 $m$ 的十进制表示，让我们来求它在这种不定进制下的表示法。（这的确是作者刚开始的灵感）如果还是看不出来，那么我们把它转化一下：

我们把这个式子的求和与求积符号去掉，原式变成：
$$ a _ 1 a _ 2 a _ 3 \cdots a _ {n - 1} b _ n + a _ 1 a _ 2 a _ 3 \cdots a _ {n - 2} b _ {n - 1} + a _ 1 a _ 2 a _ 3 \cdots a _ {n - 3} b _ {n - 2} + \cdots + a _ 1 a _ 2 b _ 3 + a _ 1 b _ 2 + b _ 1 = m $$

$$ （而 k 进制则是这样：k ^ {n - 1} b _ n + k ^ {n - 2} b _ n + \cdots + k b _ 2 + b _ 1 = m，是不是很像？） $$

用乘法分配律（类似秦九韶算法）来处理一下这个多项式，得到：（是不是跟进制转换很像？）
$$ a _ 1 [a _ 2 (a _ 3 \times \cdots + b _ 3) + b _ 2] + b _ 1 = m $$

$$ （而 k 进制则是这样：k[k(k \times \cdots + b _ 3) + b _ 2] + b _ 1 = m，是不是很像？） $$

然后我们发现，上式的最后一个加号之前的式子一定是 $a _ 1$ 的倍数，那么由于 $m = a _ i \lfloor {m \over a _ i} \rfloor + m \bmod a _ i$，后面的 $m \bmod a _ i$ 肯定就是由加号后面的 $b _ 1$ 产生的！又因为 $b _ 1 < a _ 1$，所以 $b _ 1$ 只能等于 $m \bmod a _ 1$。

同样地，当我们把上述式子两边同时减去 $b _ 1$ 再除以 $a _ 1$ 后，得到 $a _ 2 (a _ 3 \times \cdots + b _ 3) + b _ 2 = m ^ \prime$，其中 $m ^ \prime = \frac {m - b _ 1} {a _ 2} = \lfloor {m \over a _ 2} \rfloor$。同理，我们又得到 $b _ 2 = m \bmod a _ 2$。

就这样，我们就可以依次得到 $b _ 1 \sim b _ n$ 的值。

AC Code

// 这题虽然思路难想，代码却很好写
#include <cstdio>
#define N 25
using namespace std;

int n, m, a[N];

int main ()
{
    scanf ("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++)
    {
        scanf ("%d", &a[i]);
    }
    for (int i = 1; i <= n; i ++)
    {
        printf ("%d ", m % a[i]), m /= a[i];
        // 每次输出 b[i] 的值（当前 m mod a[i]），再将 m 除以 a[i] 并向下取整（int 型自动向 0 取整）
    }
    return 0;
}

超短代码：

#include<cstdio>
int n,m,a[25];
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)   scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)   printf("%d ",m%a[i]),m/=a[i];
    return 0;
}

感谢观看！

上一篇

下一篇

$$\href {/blog/content/29204/} {\color {LimeGreen} {【寒假每日一题】题解}}$$