【CSP】202209-1_如此编码Python实现

试题编号

202209-1

---

试题名称

如此编码

---

时间限制

1.0s

---

内存限制

512.0MB

---

题目背景

• 某次测验后，顿顿老师在黑板上留下了一串数字$23333$便飘然而去，凝望着这个神秘数字，小$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$，$\cdots$，$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{array}{rl}m& =\sum _{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{array}$$

• 易知，$0\le m<c_n$，最小值和最大值分别当$b_i$全部为$0$和$b_i=a_i-1$时取得
• 试帮助小$P$同学，把测验的正确答案$b_1$，$b_2$，$\cdots$，$b_n$从顿顿老师留下的神秘整数$m$中恢复出来

---

输入格式

• 从标准输入读入数据
• 输入共两行
• 第一行包含用空格分隔的两个整数$n$和$m$，分别表示题目数量和顿顿老师的神秘数字
• 第二行包含用空格分隔的$n$个整数$a_1$，$a_2$，$\cdots$，$a_n$，依次表示每道选择题的选项数目

---

输出格式

• 输出到标准输出
• 输出仅一行，包含用空格分隔的$n$个整数$b_1$，$b_2$，$\cdots$，$b_n$，依次表示每道选择题的正确选项

---

样例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解释

$i$	$1$	$2$	$3$	$4$	$5$	$6$	$7$
$a_i$	$3$	$5$	$20$	$10$	$4$	$3$	$10$
$b_i$	$2$	$2$	$15$	$7$	$3$	$1$	$0$
$c_{i-1}$	$1$	$3$	$15$	$300$	$3000$	$12000$	$36000$

---

子任务

• $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\le j\le n$，因为$c_{j+1}$，$c_{j+2}$，$\cdots$均为$c_j$的倍数，所以$m$除以$c_j$的余数具有如下性质：

$$m\%c_j=\sum _{i=1}^j{c}_{i-1}\times b_i$$

• 其中$\%$表示取余运算，令$j$取不同的值，则有如下等式：

$$\begin{array}{rl}m\%c_1& =c_0\times b_1\\ m\%c_2& =c_0\times b_1+c_1\times b_2\\ m\%c_2& =c_0\times b_1+c_1\times b_2+c_2\times b_3\end{array}$$

---

Python实现

n, m = map(int, input().split())
a = list(map(int, input().split()))b = []
c = 1for i in range(n):temp = cc *= a[i]b.append((m % c) // temp)print(*b)

---