You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

33DAI 写了一个很菜的随机数生成器，输入了随机数种子 $seed$ 和个数 $n$ 后，可以得到 $n$ 个 $0\sim 2^{64}-1$ 之间的正整数。

#include <bits/stdc++.h>
using namespace std;
unsigned long long seed;
unsigned long long rnd()
{
    seed = seed * seed + seed + 30ull;
    return seed;
}
int main()
{
    cin >> seed;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cout << rnd() << " ";
    return 0;
}

比如输入 33 10 可以得到下面的输出：

1152 1328286 1764345026112 6861985357762111070 1901262918123106560 7641831279628562718 7446905973427220672 5420652848451272926 7399983410558501248 17740564155584332190 

Kitten 决定测试一下这个随机数生成器到底有多菜，于是指定了随机数种子 $seed$ 和随机数个数 $n$，让 33DAI 生成出来 $n$ 个随机数。

紧接着给了他 $m$ 个整数 $a_1\sim a_m$，让数数看看这 $m$ 个整数中有多少个在那 $n$ 个随机数中出现了。

输入格式

第一行为三个整数 $seed,n,m$。

第二行为空格隔开的 $m$ 个整数 $a_1\sim a_m$。

输出格式

一行为一个整数，即题目说的数量。

33 10 5
33 1764345026112 1153 1152 17740564155584332190

3

样例 1 解释

生成的 $10$ 个随机数就是题目描述中的那些。下面 [] 框住的三个整数都出现了。

33 [1764345026112] 1153 [1152] [17740564155584332190]

33 10 20
1152 1328286 1764345026112 6861985357762111070 1901262918123106560 7641831279628562718 7446905973427220672 5420652848451272926 7399983410558501248 17740564155584332190 1152 1328286 1764345026112 6861985357762111070 1901262918123106560 7641831279628562718 7446905973427220672 5420652848451272926 7399983410558501248 17740564155584332190 

20

样例 2 解释

Kitten 可能会给重复的整数，需要重复计算。

33 5 2
1152 1328286

2

33 5 10
1152 1328286 1764345026112 6861985357762111070 1901262918123106560 7641831279628562718 7446905973427220672 5420652848451272926 7399983410558501248 17740564155584332190

5

样例 5

• random5.in
• random5.ans

样例 6

• random6.in
• random6.ans

数据规模与约定

对于 $100\%$ 的数据，$1\le seed,n\le 10^7$，$1\le m\le 10^5$，$0\le a_i\le 2^{64}-1$。

• 子任务 1（10 分）：保证 Kitten 的 $m$ 个随机数是使用 33DAI 的程序，输入 $seed$ 和 $m$ 生成出来的。
• 子任务 2（20 分）：保证 $m=1$。
• 子任务 3（30 分）：保证 $n\le m$。
• 子任务 4（40 分）：没有特殊限制。