#D0289. 随机重复

随机重复

题目描述

33DAI 写了一个很菜的随机数生成器,输入了随机数种子 seedseed 和个数 nn 后,可以得到 nn026410\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 决定测试一下这个随机数生成器到底有多菜,于是指定了随机数种子 seedseed 和随机数个数 nn,让 33DAI 生成出来 nn 个随机数。

紧接着给了他 mm 个整数 a1ama_1\sim a_m,让数数看看这 mm 个整数中有多少个在那 nn 个随机数中出现了。

输入格式

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

第二行为空格隔开的 mm 个整数 a1ama_1\sim a_m

输出格式

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

33 10 5
33 1764345026112 1153 1152 17740564155584332190
3

样例 1 解释

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

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

样例 6

数据规模与约定

对于 100%100\% 的数据,1seed,n1071\le seed,n\le 10^71m1051\le m\le 10^50ai26410\le a_i\le 2^{64}-1

  • 子任务 1(10 分):保证 Kitten 的 mm 个随机数是使用 33DAI 的程序,输入 seedseedmm 生成出来的。
  • 子任务 2(20 分):保证 m=1m=1
  • 子任务 3(30 分):保证 nmn\le m
  • 子任务 4(40 分):没有特殊限制。