「GOI-R1」 合成台 官方题解

虚空星胜 · 2022-08-21 11:30:34 · 个人记录

合成台 官方题解

题目描述

一次转圣操作定义为：向合成台中投入 n 个物品，使投入的 n 个物品中，每 s 个将变为 1 个新的物品，而不足 s 个的部分将保留。注意，所有物品（包括新的物品与被保留的物品）均等价 。

你拥有 n 个物品，并将其反复进行转圣操作。

你需要求出在整个过程最后（即剩余物品数量不足 s 时），你所剩余物品的数量。

数据范围

对于 100 \% 的数据，保证 1 \leq t \leq 10^5，2 \leq s \leq 10^6，0 \leq n < 10^{100}。

题解

Subtask 1

20 暴力分。理论上复杂度为 O(t \log{n})。

Subtask 2

首先，当 n=0 时，全部转圣显然会获得 0 个物品。

当 n>0 时，不妨设 n=3k+r\;(0\le r<3)，那么经过一次转圣操作后，就会得到 k+r 个物品。

显然 3k+r 和 k+r 同奇偶，所以每次转圣操作后，物品数的奇偶不会改变。

通过反证法，不难证明最后得到的物品一定为 1 个或 2 个。

所以当 n 为偶数时，最后一定剩下 2 个物品；当 n 为奇数时，最后一定剩下 1 个物品。

设 f(n) 表示对 n 个物品进行转圣操作直到物品数量 <3 时得到的物品数，由上有：

但我们不可能读入 100 位的整数；我们只需要读入字符串，将最后一位对 2 取模，即可判断出 n \bmod 2 的值。注意 n=0 的特判。

Subtask 3 & Solution

与 Subtask 2 类似：

当 n>0 时，不妨设 n=sk+r\;(0\le r<s)，

经过一次转圣操作后，就会得到 k+r 个物品。

由 Subtask 2 的结论，同奇偶等价于与 2 同余，注意到这里的两个数也与 s-1 同余。

同样有：最后得到的物品数一定 \in [1,s-1]。

设 f(n) 表示对 n 个物品进行转圣操作直到物品数量 <s 时得到的物品数。由上有：

由于在 n<s 时一定有 f(n)=n，进而得出：

上式对于 1 \leq n < s 同样成立，进而得出

但我们不太可能对一个 100 位的整数减一，很繁琐；因此我们可以对其进行一些变形：

为使除数非负以不影响取模，加上一个 s-1，有：

到这里问题转化为求 n \bmod (s-1)。我们可以利用同余的性质来求出答案。

以整数 114514 举例：

我们可以将其分解为 1 \times 10^5 + 1 \times 10^4 + 4 \times 10^3 + 5 \times 10^2 + 1 \times 10^1 + 4\times 10^0。

由于取模运算具有同加性与同乘性，我们可以计算出每一位对于答案的贡献再相加取模。

以第一位为例，计算 (1 \times 10^5) \bmod (s-1) 可以将 1 与 10^5 分别取模后相乘，再进行取模并累加到答案中。

我们分别计算每一位的贡献，在计算答案的时候边相加边取模，最终就可以得到 n \bmod (s-1) 的值。

设这个整数的位数为 l，由于我们要对每一位都计算一次，因此复杂度为 O(Tl)。我们可以 O(l) 预处理出 10^i \bmod (s-1) 的值，所以总复杂度也是 O(Tl)。

注意：n=0 的特判仍然要写！小心爆零哦！

下面是代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int mod, mul10[107], len;
//预处理出 (10 ^ x) mod (s - 1) 的值
void initmul10()
{
    mul10[0] = 1 % mod; //s - 1 可能为 1
    for (int i = 1; i <= len; i++)
        mul10[i] = (mul10[i - 1] * 10) % mod;
}
//计算每一位对答案的贡献 (x * (10 ^ y)) mod (s - 1)
int calcxmul10y(int x, int y)
{
    return (x * mul10[y]) % mod;
}
//计算答案
int nmod(string n)
{
    int ans = 0;
    for (int i = 0; i < len; i++)
    {
        //字符串第 i 位为整数的第 len - i 位
        //例如：
        //       114
        // i     012
        // len-i 321
        int num = len - i, x = n[i] - '0';
        ans = (ans + calcxmul10y(x, num - 1)) % mod;
    }
    return ans;
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int s;
        string n;
        cin >> s >> n;
        if (n == "0")
        {
            cout << "0\n";
            continue;
        }
        mod = s - 1;
        len = n.size();
        initmul10();
        int ans = 1 + (nmod(n) + s - 2) % mod;
        cout << ans << '\n';
    }
    return 0;
}

为什么不是 AC 代码呢？因为它 T 了...

Subtask 4

本题在题面中给出了常数预警，而想到常数优化，第一个想到的自然是——

快读！

然而对于这样大的一个整数，无论怎样读取都是无法存储的。

稍加思考，不难发现在本题中我们需要知道 n 的以下信息：

• n$ 是否为 $0

前者自然可以用快读处理；

而对于后者，思考快读的核心操作：

char ch = getchar();
x *= 10;
x += ch - '0';

其中只包含了加法与乘法运算。

因此，我们可以一边快读一边进行取模操作，这样自然就知道了 n \bmod (s-1) 的值。

将其与 Subtask 3 的做法对比，Subtask 3 的做法需要：

• 读入字符串，O(Tl)

• 预处理 10^i \bmod (s-1)，O(Tl)

• 计算 n \bmod (s-1)，O(Tl)

而本做法只需要第一项的 O(Tl)，相当于少了 \dfrac{1}{3} 的常数。事实上，由于原做法大量进行乘法、取模运算，本做法的常数更具优势。

下面是 AC 代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>

using namespace std;

bool is_zero = false; //判断是否是0

inline int read(int mod)
{ //快读,边读入边取模
    int x = 0;
    char ch = getchar();
    while (!isdigit(ch))
        ch = getchar();
    int i = 0; //记录读到从前往后第几位
    while (isdigit(ch))
    {
        x = 10 * x + ch - '0';
        if (ch == '0' && !i)
            is_zero = true; //如果第一位就是0,说明这个数为0
        x %= mod;             //取模
        ch = getchar();
        i++;
    }
    return x;
}

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        is_zero = false;
        int s;
        scanf("%d", &s);
        int n = read(s - 1); //读入时对s-1取模

        if (is_zero && !n)
            puts("0"); //特判n=0
        else
        {
            n = (n + s - 2) % (s - 1) + 1;
            printf("%d\n", n);
        }
    }
    return 0;
}

鸣谢

Subtask 1

Subtask 2: Jasper08

Subtask 3: idea: Hoshino_kaede，YYHDoggy，code: YYHDoggy

Subtask 4: idea & code: Jasper08