CCF计算机软件能力认证考试—202209-1如此编码

题目背景

某次测验后，顿顿老师在黑板上留下了一串数字 23333 便飘然而去。凝望着这个神秘数字，小 P 同学不禁陷入了沉思……

题目描述

已知某次测验包含 � 道单项选择题，其中第 � 题（1≤�≤�）有 �� 个选项，正确选项为 ��，满足 ��≥2 且 0≤��<��。比如说，��=4 表示第 � 题有 4 个选项，此时正确选项 �� 的取值一定是 0、1、2、3 其中之一。

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

首先定义一个辅助数组 ��，表示数组 �� 的前缀乘积。当 1≤�≤� 时，满足：
��=�1×�2×⋯×��

特别地，定义 �0=1。

于是 � 便可按照如下公式算出：
�=∑�=1���−1×��=�0×�1+�1×�2+⋯+��−1×��

易知，0≤�<��，最小值和最大值分别当 �� 全部为 0 和 ��=��−1 时取得。

试帮助小 � 同学，把测验的正确答案 �1,�2,⋯,�� 从顿顿老师留下的神秘整数 � 中恢复出来。

输入格式

从标准输入读入数据。

输入共两行。

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

第二行包含用空格分隔的 � 个整数 �1,�2,⋯,��，依次表示每道选择题的选项数目。

输出格式

输出到标准输出。

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

样例1输入

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

Data

样例1输出

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

Data

样例2输入

4 0
2 3 2 5

Data

样例2输出

0 0 0 0

Data

样例3输入

7 23333
3 5 20 10 4 3 10

Data

样例3输出

2 2 15 7 3 1 0

Data

样例3解释

�	1	2	3	4	5	6	7
��	3	5	20	10	4	3	10
��	2	2	15	7	3	1	0
��−1	1	3	15	300	3000	12000	36000

子任务

50% 的测试数据满足：�� 全部等于 2，即每道题均只有两个选项，此时 ��=2�；

全部的测试数据满足：1≤�≤20，��≥2 且 ��≤109（根据题目描述中的定义 �� 表示全部 �� 的乘积）。

提示

对任意的 1≤�≤�，因为 ��+1,��+2,⋯ 均为 �� 的倍数，所以 � 除以 �� 的余数具有如下性质：
� % ��=∑�=1���−1×��
其中 % 表示取余运算。令 � 取不同的值，则有如下等式：

#include<iostream>
using namespace std;
int main()
{int n,i,j,m,a[1000],b[1000],c[1000],s[1000];c[0]=1,s[0]=0;cin>>n>>m;//表示题目数量和神秘数字for(i=1;i<=n;i++){cin>>a[i];//定义a数组 for(j=1;j<=i;j++){ c[j]=c[j-1]*a[j];//定义c数组s[j]=m%c[j];//定义s数组}}for(i=1;i<=n;i++)//定义b数组 {b[i]=(s[i]-s[i-1])/c[i-1];}for(i=1;i<=n;i++)//输出b数组 {cout<<b[i]<<" ";} return 0;}