「PMOI-4」人赢的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者： admin

概述

给定数列的前两项 $a_1 = n$ ~a_1 = n~、 $a_2 = m$ ~a_2 = m~（ $0 \le n, m \le 9$ ~0 \le n, m \le 9~），从第三项起每一项都是前两项乘积的个位数：

$\displaystyle a_i = a_{i-2} \times a_{i-1} \bmod 10 \qquad (i > 2)$

再给定位置 $k$ ~k~（ $1 \le k \le 10^{12}$ ~1 \le k \le 10^{12}~），要求输出 $a_k$ ~a_k~。

直接按定义递推需要 $O(k)$ ~O(k)~ 的时间，而 $k$ ~k~ 最大可以到 $10^{12}$ ~10^{12}~，在 1 秒的时限内显然做不到。但每一项都只有 $10$ ~10~ 种取值，相邻两项组成的「状态」只有 $100$ ~100~ 种，所以数列必然在很短的距离内进入循环。本题的全部内容就是发现并利用这个循环。

分析

核心观察

把相邻两项作为一个整体来看：

每一项都由前两项完全确定，即 $a_i$ ~a_i~ 只取决于 $(a_{i-2}, a_{i-1})$ ~(a_{i-2}, a_{i-1})~；
每一项的取值范围都是 $0 \sim 9$ ~0 \sim 9~，所以有序二元组 $(a_{i-1}, a_i)$ ~(a_{i-1}, a_i)~ 最多只有 $10 \times 10 = 100$ ~10 \times 10 = 100~ 种。

从下标 $2$ ~2~ 开始考察状态序列 $s_2 = (a_1, a_2), s_3 = (a_2, a_3), s_4 = (a_3, a_4), \ldots$ ，它一共只有 $100$ ~100~ 种可能的取值。根据抽屉原理，第 $101$ ~101~ 个状态（即 $s_{102}$ ~s_{102}~）必定与它前面的某个状态相同；换句话说，只要模拟不超过 $101$ ~101~ 步，就一定能找到两个下标 $j < i$ ~j < i~ 满足 $(a_{j-1}, a_j) = (a_{i-1}, a_i)$ ~(a_{j-1}, a_j) = (a_{i-1}, a_i)~。

状态相同就意味着后续完全相同：从 $(a_{j-1}, a_j)$ ~(a_{j-1}, a_j)~ 与从 $(a_{i-1}, a_i)$ ~(a_{i-1}, a_i)~ 出发走的是同一个递推过程，因此对一切 $t \ge j$ ~t \ge j~ 都有 $a_t = a_{t + (i - j)}$ ~a_t = a_{t + (i - j)}~，即数列从第 $j$ ~j~ 项开始以 $p = i - j$ ~p = i - j~ 为周期循环。

一旦求出 $(j, p)$ ~(j, p)~，任意大的 $k$ ~k~ 都能 $O(1)$ ~O(1)~ 回答：

$\displaystyle a_k = a_{j + ((k - j) \bmod p)} \qquad (k \ge j)$

下标 $j + ((k - j) \bmod p)$ ~j + ((k - j) \bmod p)~ 落在 $[j,\, i - 1]$ ~[j,\, i - 1]~ 内，都是模拟时已经算出来的位置。

思路

直接按定义模拟，同时记下每个状态第一次出现的位置：

若状态 $(x, y)$ ~(x, y)~ 第一次出现在下标 $h$ ~h~（即 $s_h = (a_{h-1}, a_h)$ ~s_h = (a_{h-1}, a_h)~），就记下这个 $h$ ~h~；
模拟到下标 $i$ ~i~ 时发现 $s_i$ ~s_i~ 已经出现过，设它第一次出现的位置是 $j$ ~j~，则循环节长度 $p = i - j$ ~p = i - j~，答案用上面的公式给出；
若还没发现循环就已经模拟到了 $k$ ~k~（ $k$ ~k~ 很小的情况），直接输出 $a_k$ ~a_k~ 即可。

另外题面只保证 $k \ge 1$ ~k \ge 1~，而递推式只对 $i > 2$ ~i > 2~ 成立，因此 $k = 1$ ~k = 1~ 与 $k = 2$ ~k = 2~ 必须单独回答 $n$ ~n~ 和 $m$ ~m~，不能丢进模拟里。

由于 $k$ ~k~ 最大 $10^{12}$ ~10^{12}~，模拟步数必须与 $k$ ~k~ 无关；好在循环必然在前 $101$ ~101~ 步内出现，算法天然满足这一点。

具体示例

样例 1： $n = 1, m = 6, k = 10$ ~n = 1, m = 6, k = 10~。

逐项计算： $a_3 = 1 \times 6 \bmod 10 = 6$ ~a_3 = 1 \times 6 \bmod 10 = 6~，其后的每一项都是 $6 \times 6 \bmod 10 = 6$ ~6 \times 6 \bmod 10 = 6~，于是数列是 $1, 6, 6, 6, \ldots$ ~1, 6, 6, 6, \ldots~。

模拟过程：

状态 $(a_1, a_2) = (1, 6)$ ~(a_1, a_2) = (1, 6)~ 出现在下标 $2$ ~2~；
下标 $3$ ~3~： $a_3 = 6$ ~a_3 = 6~，状态 $(6, 6)$ ~(6, 6)~ 第一次出现，记在下标 $3$ ~3~；
下标 $4$ ~4~： $a_4 = 6$ ~a_4 = 6~，状态 $(6, 6)$ ~(6, 6)~ 已经出现过，第一次出现在下标 $3$ ~3~，于是 $j = 3$ ~j = 3~、 $p = 4 - 3 = 1$ ~p = 4 - 3 = 1~；
$k = 10 \ge 3$ ~k = 10 \ge 3~，答案为 $a_{3 + ((10 - 3) \bmod 1)} = a_3 = 6$ ~a_{3 + ((10 - 3) \bmod 1)} = a_3 = 6~。

样例 2： $n = 7, m = 2, k = 7$ ~n = 7, m = 2, k = 7~。

前几项每一项分别是前两项乘积的个位数，得到：

下标	$1$ ~1~	$2$ ~2~	$3$ ~3~	$4$ ~4~	$5$ ~5~	$6$ ~6~	$7$ ~7~	$8$ ~8~	$9$ ~9~
$a_i$ ~a_i~	$7$ ~7~	$2$ ~2~	$4$ ~4~	$8$ ~8~	$2$ ~2~	$6$ ~6~	$2$ ~2~	$2$ ~2~	$4$ ~4~

这里 $a_7 = 2$ ~a_7 = 2~，模拟到第 $7$ ~7~ 项就直接得到答案 $2$ ~2~。

如果继续模拟下去，下标 $9$ ~9~ 的状态 $(a_8, a_9) = (2, 4)$ ~(a_8, a_9) = (2, 4)~ 会与下标 $3$ ~3~ 的状态 $(a_2, a_3) = (2, 4)$ ~(a_2, a_3) = (2, 4)~ 相同，于是 $j = 3$ ~j = 3~、 $p = 6$ ~p = 6~；用公式验证： $a_{3 + ((7 - 3) \bmod 6)} = a_7 = 2$ ~a_{3 + ((7 - 3) \bmod 6)} = a_7 = 2~，与直接模拟一致。注意这个数列的循环并不是从第一项就开始的，开头的 $7, 2$ ~7, 2~ 并不参与循环——这正是取模定位时必须带上起点 $j$ ~j~ 的原因。

顺便一提，把全部 $100$ ~100~ 种 $(n, m)$ ~(n, m)~ 都模拟一遍可以发现：循环起点 $j$ ~j~ 总是 $2$ ~2~、 $3$ ~3~ 或 $4$ ~4~，循环节长度 $p$ ~p~ 总是 $1$ ~1~、 $3$ ~3~ 或 $6$ ~6~（其中 $p = 6$ ~p = 6~ 有 $48$ ~48~ 种组合）。这也说明 $100$ ~100~ 个状态足以保证循环出现得足够早。

算法步骤

读入三个整数 $n, m, k$ ~n, m, k~，其中 $k$ ~k~ 要按 64 位整数处理。
若 $k = 1$ ~k = 1~，输出 $n$ ~n~；若 $k = 2$ ~k = 2~，输出 $m$ ~m~；直接结束。
令 $a_1 = n$ ~a_1 = n~、 $a_2 = m$ ~a_2 = m~，把状态 $(n, m)$ ~(n, m)~ 第一次出现的位置记为 $2$ ~2~。
从 $i = 3$ ~i = 3~ 开始循环：
1. 计算 $a_i = a_{i-1} \times a_{i-2} \bmod 10$ ~a_i = a_{i-1} \times a_{i-2} \bmod 10~；
2. 若 $i = k$ ~i = k~，输出 $a_i$ ~a_i~ 并结束（ $k$ ~k~ 很小、还没进入循环的情况）；
3. 若状态 $(a_{i-1}, a_i)$ ~(a_{i-1}, a_i)~ 之前出现过，设第一次出现的位置为 $j$ ~j~，令 $p = i - j$ ~p = i - j~，输出 $a_{j + ((k - j) \bmod p)}$ ~a_{j + ((k - j) \bmod p)}~ 并结束；
4. 否则记下状态 $(a_{i-1}, a_i)$ ~(a_{i-1}, a_i)~ 第一次出现的位置为 $i$ ~i~，进入下一个 $i$ ~i~。
循环最多执行 $101$ ~101~ 次，就一定会因为状态重复而结束。

复杂度分析

时间复杂度：模拟步数不超过 $101$ ~101~ 步（ $101$ ~101~ 个状态里必有两个相同），每步都是常数次运算，所以总时间是 $O(\min(k, 101))$ ~O(\min(k, 101))~，即 $O(1)$ ~O(1)~，与 $k$ ~k~ 的大小无关。作为对比，直接递推到第 $k$ ~k~ 项是 $O(k)$ ~O(k)~，在 $k = 10^{12}$ ~k = 10^{12}~ 时无法通过。
空间复杂度：只需要存常数项数列（ $110$ ~110~ 个位置足够）和 $100$ ~100~ 个状态第一次出现的位置，即 $O(1)$ ~O(1)~。

实现注意事项

$k \le 10^{12}$ ~k \le 10^{12}~ 超出了 32 位整数的范围，C++ 里必须用 long long，读入用 %lld；Python 的整数没有这个问题。
$k = 1$ ~k = 1~ 与 $k = 2$ ~k = 2~ 必须特判：递推式从第 $3$ ~3~ 项才生效，下标 $1$ ~1~、 $2$ ~2~ 的答案由输入直接给出。
「状态还没出现过」的标记不要和合法下标混在一起。本题把初始状态记在下标 $2$ ~2~、其余状态记在下标 $\ge 3$ ~\ge 3~，所以用 $0$ ~0~ 表示未出现也是安全的，但显式写 $-1$ ~-1~ 更不容易出错。
$n = 0$ ~n = 0~ 或 $m = 0$ ~m = 0~ 是合法输入（此时从第三项起全是 $0$ ~0~），不要当作非法数据特判掉。
所有项都是非负的，% 10 就是题面所说的「个位数」，不需要处理负数取模。
数组开到 $110$ ~110~ 以上就够了（循环必然在前 $101$ ~101~ 步内出现），不要按 $k$ ~k~ 的大小开数组，更不要真的递推 $k$ ~k~ 步。
输出是单个数字加换行。

源代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n, m, k;
    if (scanf("%lld %lld %lld", &n, &m, &k) != 3) return 0;

    // 递推只对 i > 2 成立，前两项由输入直接给出。
    if (k == 1) { printf("%lld\n", n); return 0; }
    if (k == 2) { printf("%lld\n", m); return 0; }

    static int a[128];
    static int firstAt[10][10];  // firstAt[x][y]：状态 (x, y) 第一次出现的位置，0 表示还没出现
    memset(firstAt, 0, sizeof(firstAt));

    a[1] = (int)n;
    a[2] = (int)m;
    firstAt[a[1]][a[2]] = 2;     // 初始状态 (a1, a2) 出现在位置 2

    for (int i = 3; ; ++i) {
        a[i] = a[i - 1] * a[i - 2] % 10;
        if (i == k) { printf("%d\n", a[i]); return 0; }  // k 很小，没等到循环

        int x = a[i - 1], y = a[i];
        if (firstAt[x][y] != 0) {
            int j = firstAt[x][y];               // 循环从位置 j 开始
            int p = i - j;                       // 循环节长度
            printf("%d\n", a[j + (int)((k - j) % p)]);
            return 0;
        }
        firstAt[x][y] = i;
    }
}

import sys


def main():
    data = sys.stdin.read().split()
    n, m, k = int(data[0]), int(data[1]), int(data[2])

    if k == 1:
        print(n)
        return
    if k == 2:
        print(m)
        return

    a = [0, n, m]           # a[1] = n, a[2] = m
    first_at = {(n, m): 2}  # 状态 (a[i-1], a[i]) 第一次出现的位置

    i = 3
    while True:
        a.append(a[i - 1] * a[i - 2] % 10)
        if i == k:
            print(a[i])
            return

        key = (a[i - 1], a[i])
        if key in first_at:
            j = first_at[key]
            p = i - j
            print(a[j + (k - j) % p])
            return
        first_at[key] = i
        i += 1


main()

目前没有评论。