河南做网站哪个平台好,如何建立微信群,app开发网站开发,soapclient WordPress文章目录 [toc]试题编号试题名称时间限制内存限制题目背景题目描述输入格式输出格式样例1输入样例1输出样例2输入样例2输出样例3输入样例3输出样例3解释子任务提示Python实现 试题编号 202209-1 试题名称 如此编码 时间限制 1.0s 内存限制 512.0MB 题目背景
某次测验后#x… 文章目录 [toc]试题编号试题名称时间限制内存限制题目背景题目描述输入格式输出格式样例1输入样例1输出样例2输入样例2输出样例3输入样例3输出样例3解释子任务提示Python实现
试题编号
202209-1 试题名称
如此编码 时间限制
1.0s 内存限制
512.0MB 题目背景
某次测验后顿顿老师在黑板上留下了一串数字 23333 23333 23333便飘然而去凝望着这个神秘数字小 P P P同学不禁陷入了沉思 题目描述
已知某次测验包含 n n n道单项选择题其中第 i i i题 ( 1 ≤ i ≤ n ) (1 \leq i \leq n) (1≤i≤n)有 a i a_{i} ai个选项正确选项为 b i b_{i} bi满足 a i ≥ 2 a_{i} \geq 2 ai≥2且 0 ≤ b i a i 0 \leq b_{i} a_{i} 0≤biai比如说 a i 4 a_{i} 4 ai4表示第 i i i题有 4 4 4个选项此时正确选项 b i b_{i} bi的取值一定是 0 0 0、 1 1 1、 2 2 2、 3 3 3其中之一顿顿老师设计了如下方式对正确答案进行编码使得仅用一个整数 m m m便可表示 b 1 b_{1} b1 b 2 b_{2} b2 ⋯ \cdots ⋯ b n b_{n} bn首先定义一个辅助数组 c i c_{i} ci表示数组 a i a_{i} ai的前缀乘积当 1 ≤ i ≤ n 1 \leq i \leq n 1≤i≤n时满足 c i a 1 × a 2 × ⋯ × a i c_{i} a_{1} \times a_{2} \times \cdots \times a_{i} cia1×a2×⋯×ai
特别地定义 c 0 1 c_{0} 1 c01于是 m m m便可按照如下公式算出 m ∑ i 1 n c i − 1 × b i c 0 × b 1 c 1 × b 2 ⋯ c n − 1 × b n \begin{aligned} m \displaystyle\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{aligned} mi1∑nci−1×bic0×b1c1×b2⋯cn−1×bn
易知 0 ≤ m c n 0 \leq m c_{n} 0≤mcn最小值和最大值分别当 b i b_{i} bi全部为 0 0 0和 b i a i − 1 b_{i} a_{i} - 1 biai−1时取得试帮助小 P P P同学把测验的正确答案 b 1 b_{1} b1 b 2 b_{2} b2 ⋯ \cdots ⋯ b n b_{n} bn从顿顿老师留下的神秘整数 m m m中恢复出来 输入格式
从标准输入读入数据输入共两行第一行包含用空格分隔的两个整数 n n n和 m m m分别表示题目数量和顿顿老师的神秘数字第二行包含用空格分隔的 n n n个整数 a 1 a_{1} a1 a 2 a_{2} a2 ⋯ \cdots ⋯ a n a_{n} an依次表示每道选择题的选项数目 输出格式
输出到标准输出输出仅一行包含用空格分隔的 n n n个整数 b 1 b_{1} b1 b 2 b_{2} b2 ⋯ \cdots ⋯ b n b_{n} bn依次表示每道选择题的正确选项 样例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 i i 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 a i a_{i} ai 3 3 3 5 5 5 20 20 20 10 10 10 4 4 4 3 3 3 10 10 10 b i b_{i} bi 2 2 2 2 2 2 15 15 15 7 7 7 3 3 3 1 1 1 0 0 0 c i − 1 c_{i - 1} ci−1 1 1 1 3 3 3 15 15 15 300 300 300 3000 3000 3000 12000 12000 12000 36000 36000 36000 子任务 50 % 50\% 50%的测试数据满足 a i a_{i} ai全部等于 2 2 2即每道题均只有两个选项此时 c i 2 i c_{i} 2^{i} ci2i全部的测试数据满足 1 ≤ n ≤ 20 1 \leq n \leq 20 1≤n≤20 a i ≥ 2 a_{i} \geq 2 ai≥2且 c n ≤ 1 0 9 c_{n} \leq 10^{9} cn≤109根据题目描述中的定义 c n c_{n} cn表示全部 a i a_{i} ai的乘积 提示
对任意的 1 ≤ j ≤ n 1 \leq j \leq n 1≤j≤n因为 c j 1 c_{j 1} cj1 c j 2 c_{j 2} cj2 ⋯ \cdots ⋯均为 c j c_{j} cj的倍数所以 m m m除以 c j c_{j} cj的余数具有如下性质 m % c j ∑ i 1 j c i − 1 × b i m \% c_{j} \displaystyle\sum\limits_{i 1}^{j}{c_{i - 1} \times b_{i}} m%cji1∑jci−1×bi
其中 % \% %表示取余运算令 j j j取不同的值则有如下等式 m % c 1 c 0 × b 1 m % c 2 c 0 × b 1 c 1 × b 2 m % c 2 c 0 × b 1 c 1 × b 2 c 2 × b 3 \begin{aligned} 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{aligned} m%c1m%c2m%c2c0×b1c0×b1c1×b2c0×b1c1×b2c2×b3 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)
