#D. 一道非常简单的排序题

    传统题 1000ms 256MiB

一道非常简单的排序题

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

题目描述

33DAI 定义了一个函数:

int seed, P; // 通过输入得到
int f(int id)
{
    return 1LL * id * id % P * seed % P;
}

33DAI 用这个函数生成了一个长度为 nn 序列 aa,下标从 1n1\sim n,第 ii 个数 aia_i 的值为 f(i)f(i)

请你将这个序列排序,保证每个数都大于或等于它后面的数,即 a1a2ana_1\ge a_2\ge \dots \ge a_n

然后输出“每个元素与其下标之和”的异或和。即排序后的 (a1+1)(a2+2)(an+n)(a_1+1)\oplus (a_2+2)\oplus \dots\oplus (a_n+n)

异或:数学中用 \oplus 符号表示异或和,C++ 中可以使用 a^b 算出两个数的异或和。由于异或和运算属于位运算,优先级非常低,建议所有涉及位运算的表达式都多用小括号来保证运算符优先级正确。

输入格式

输入三个整数 n,seed,Pn,seed,P

输出格式

输出题目要求的“每个元素与其下标之和”的异或和。

5 33 100
92

样例解释

得到的序列为 {33,32,97,28,25}\{33,32,97,28,25\},排序后为 {97,33,32,28,25}\{97,33,32,28,25\}

$(97+1)\oplus(33+2)\oplus(32+3)\oplus(28+4)\oplus(25+5)=92$

5000000 33 998244353
1069767311

数据规模与约定

对于 100%100\% 的数据,1n5×1061 \le n \le 5\times 10^61seed,P1091\le seed,P\le 10^9

  • 子任务 1(30 分):保证 n=1n=1
  • 子任务 2(30 分):保证 n1000n\le 1000
  • 子任务 3(40 分):没有特殊限制

挖土机周赛 Round 31(语法场)

未参加
状态
已结束
规则
乐多
题目
4
开始于
2024-11-8 19:00
结束于
2024-11-10 22:00
持续时间
2 小时
主持人
参赛人数
143