摘要
Title: 4699. 如此编码
Tag: 取模
Memory Limit: 64 MB
Time Limit: 1000 ms

4699. 如此编码

题意

第27次CCF计算机软件能力认证

某次测验后，顿顿老师在黑板上留下了一串数字 23333 便飘然而去。
凝望着这个神秘数字，小 P 同学不禁陷入了沉思……
已知某次测验包含 n 道单项选择题，其中第 i 题（1≤i≤n）有 ai 个选项，正确选项为 bi，满足 ai≥2 且 0≤bi<ai。
比如说，ai=4 表示第 i 题有 4 个选项，此时正确选项 bi 的取值一定是 0、1、2、3 其中之一。
顿顿老师设计了如下方式对正确答案进行编码，使得仅用一个整数 m 便可表示 b1,b2,⋯,bn。
首先定义一个辅助数组 ci，表示数组 ai 的前缀乘积。
易知，0≤m<cn，最小值和最大值分别当 bi 全部为 0 和 bi=ai−1 时取得。
试帮助小 P 同学，把测验的正确答案 b1,b2,⋯,bn 从顿顿老师留下的神秘整数 m 中恢复出来。
思路

根据题目的信息，创造出多个方程
- $c_j = \prod_{i=1}^{j}a_i$ ，可以看出 $c_j$ 是 $c_{j-1}$ 的倍数
- $m = \sum_{i=1}^n c_{i-1}* b_i$ $m = \sum_{i = 1}^{n} c_{i - 1} * b_{i}$ ，根据这个等式，再结合等式1，可以看出
  - $m\%c_1 = c_0*b_1$
  - $m\%c_2 = c_0*b_1 + c_1*b_2$
  - ……
- 也就是说，根据上面，做个前缀和逆运算，可以得到 $c_i b_{i-1}$ 数组，从而可求出 $b$ 数组

代码

/*
* @Author: NEFU AB-IN
* @Date: 2023-01-12 12:23:41
* @FilePath: \Acwing\4699\4699.cpp
* @LastEditTime: 2023-01-12 12:47:52
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

signed main()
{
    IOS;
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1), c(n + 1), mc(n + 1), cb(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    c[0] = 1;
    for (int i = 1; i <= n; ++i)
    {
        c[i] = c[i - 1] * a[i];
    }

    for (int i = 1; i <= n; ++i)
    {
        mc[i] = m % c[i];
    }

    for (int i = 1; i <= n; ++i)
    {
        cb[i] = mc[i] - mc[i - 1];
        cout << cb[i] / c[i - 1] << " ";
    }

    return 0;
}

4699. 如此编码

题意

思路

代码