【C++】漸化式で生成される数列に含まれる異なる要素の個数を求める方法

問題概要

3つの整数 n、x、y、z が与えられます。これらの値をもとに、次のルールで数列を作成します。

• 数列の最初の項：x mod 2³¹
• 2番目以降の項：a_i = (a_(i-1) × y + z) mod 2³¹（ただし 1 ≤ i ≤ n - 1）

このようにして作成した数列に含まれる異なる整数の個数を求めるのが、この問題の目的です。

入出力例

たとえば、入力が n = 5、x = 1、y = 2、z = 1 の場合、出力は 5 になります。

実際に数列を計算すると、一意な値は {1, 3, 7, 15, 31} となるため、答えは 5 です。

解法の考え方

この問題は、以下の手順で解くことができます。

• MOD := 2³¹ と定義する
• 出現済みの値を記録するための配列 temp を用意し、サイズを MOD に設定する
• p := x mod MOD とし、temp[p] を true にする
• ans := 1 で初期化する
• i が 1 から n - 1 までの間、以下を繰り返す
  • p := ((p * y) + z) mod MOD を計算する
  • temp[p] がすでに true の場合はループを抜ける
  • そうでなければ ans を 1 増やし、temp[p] を true にする
• 最終的な ans を返す

ここで重要なのは、同じ値が一度現れた時点でループを打ち切ってよいという点です。この数列は決定的（直前の値だけで次の値が完全に決まる）なため、ある値が再び出現すると、その後は同じパターンが周期的に繰り返され、新しい異なる値は二度と現れません。

また、vector<bool> はビット単位でデータを格納するため、2³¹ 個の要素を扱ってもメモリ消費を大幅に抑えられる点も、実装上の工夫といえます。

C++による実装例

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const long long MOD = 2147483648;

int solve(int n, long long x, long long y, long long z) {
    vector<bool> temp;
    temp.resize(MOD);
    long long p = x % MOD;
    temp[p] = true;
    int ans = 1;
    for (int i = 1; i < n; ++i) {
        p = ((p * y) + z) % MOD;
        if (temp[p])
            break;
        ++ans;
        temp[p] = true;
    }
    return ans;
}

int main() {
    cout << solve(5, 1, 2, 1) << endl;
    return 0;
}

入力

5, 1, 2, 1

出力

5