传统题 1000ms 512MiB

【明月杯3E】望月

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个长度为 nn 的数列,问数列中出现次数为 1k1\sim k 的倍数的数字分别有多少种?

输入格式

由于本题的输入量过大,所以采用生成式输入。

第一行两个整数 n,kn,k

第二行两个整数,表示 s,keys,key

数组 aas,keys,key 和代码生成,请选手在提交的代码中选择合适位置生成数组 aa,这里提供cpp代码.

void decode(long long n,long long s,long long key){
    for(long long i = 1;i <= n;i++){
        a[i] = s;
        s = (25214903917 * s) & key;
    }
}

输出格式

由于本题输出量过大,所以使用加密输出。

一行 11 个整数,代表答案的平方和,请使用 64 位有符号整型自然溢出得到答案。

样例 #1

样例输入 #1

7 4
1 15

样例输出 #1

25

样例 #2

样例输入 #2

100 100
1 65535

样例输出 #2

10000

提示

样例 11 生成的 aa 数组为 1,13,9,5,1,13,91,13,9,5,1,13,9

1,5,9,131,5,9,13 出现了 2,1,2,22,1,2,2 次,所以出现次数为 11 的倍数的种类数为 44,出现次数为 22 的倍数的种类数为 33,平方和为 2525

对于 30%30\% 的数据,1n,k1051\leq n,k\leq 10^5

对于额外 30%30\% 的数据,1n,k1061\leq n,k\leq 10^6

对于 100%100\% 的数据,1n,k1071\leq n,k\leq 10^71ai1071\leq a_i\leq 10^7

明月杯3

未参加
状态
已结束
规则
OI
题目
10
开始于
2024-4-10 18:30
结束于
2024-4-10 22:30
持续时间
4 小时
主持人
参赛人数
35