随机重复

题目描述

小珅同学写了一个很菜的随机数生成器，输入了随机数种子 $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

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

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

输入格式

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

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

输出格式

共一行，一个整数，表示在 $n$个随机数中出现的 $m$个数的个数。

输入输出样例

输入 #1

33 10 5 33 1764345026112 1153 1152 17740564155584332190

输出 #1

3

输入 #2

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

输出 #2

20

输入 #3

33 5 2 1152 1328286

输出 #3

2

输入 #4

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

输出 #4

5

说明/提示

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

子任务 $1$（$10$分）：保证小泽的 $m$个随机数是使用小珅的程序，输入 $seed$和 $m$生成出来的。

子任务 $2$（$20$分）：保证 $m = 1$。

子任务 $3$（$30$分）：保证 $n \le m$。

子任务 $4$（$40$分）：没有特殊限制。