P2774 - T3-随机重复

内存限制：128 MB 时间限制：8.000 S

评测方式：文本比较命题人：

提交：11 解决：1

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

## 样例 1 解释

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

```
33 [1764345026112] 1153 [1152] [17740564155584332190]
```

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

```output2
20
```

### 样例 2 解释

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

```input3
33 5 2
1152 1328286
```

```output3
2
```

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

```output4
5
```

## 样例 5

- [random5.in](file://random5.in)
- [random5.ans](file://random5.ans)

## 样例 6

- [random6.in](file://random6.in)
- [random6.ans](file://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 分）：没有特殊限制。

2774: T3-随机重复

题目描述

输入

输出

样例输入复制

样例输出复制

提示

2774: T3-随机重复

题目描述

输入

输出

样例输入 复制

样例输出 复制

提示

样例输入复制

样例输出复制