310432: CF1832E. Combinatorics Problem
Description
Recall that the binomial coefficient $\binom{x}{y}$ is calculated as follows ($x$ and $y$ are non-negative integers):
- if $x < y$, then $\binom{x}{y} = 0$;
- otherwise, $\binom{x}{y} = \frac{x!}{y! \cdot (x-y)!}$.
You are given an array $a_1, a_2, \dots, a_n$ and an integer $k$. You have to calculate a new array $b_1, b_2, \dots, b_n$, where
- $b_1 = (\binom{1}{k} \cdot a_1) \bmod 998244353$;
- $b_2 = (\binom{2}{k} \cdot a_1 + \binom{1}{k} \cdot a_2) \bmod 998244353$;
- $b_3 = (\binom{3}{k} \cdot a_1 + \binom{2}{k} \cdot a_2 + \binom{1}{k} \cdot a_3) \bmod 998244353$, and so on.
Formally, $b_i = (\sum\limits_{j=1}^{i} \binom{i - j + 1}{k} \cdot a_j) \bmod 998244353$.
Note that the array is given in a modified way, and you have to output it in a modified way as well.
InputThe only line of the input contains six integers $n$, $a_1$, $x$, $y$, $m$ and $k$ ($1 \le n \le 10^7$; $0 \le a_1, x, y < m$; $2 \le m \le 998244353$; $1 \le k \le 5$).
The array $[a_1, a_2, \dots, a_n]$ is generated as follows:
- $a_1$ is given in the input;
- for $2 \le i \le n$, $a_i = (a_{i-1} \cdot x + y) \bmod m$.
Since outputting up to $10^7$ integers might be too slow, you have to do the following:
Let $c_i = b_i \cdot i$ (without taking modulo $998244353$ after the multiplication). Print the integer $c_1 \oplus c_2 \oplus \dots \oplus c_n$, where $\oplus$ denotes the bitwise XOR operator.
ExampleInput5 8 2 3 100 2Output
1283
Input
题意翻译
# 组合数学问题 ## 题目描述 回顾一下二项式系数 $ \binom{x}{y} $ 的计算方法（其中 $ x $ 和 $ y $ 是非负整数）： - 如果 $ x < y $ ，则 $ \binom{x}{y} = 0 $ ； - 否则，$ \binom{x}{y} = \frac{x!}{y! \cdot (x-y)!} $ 。 给定一个数组 $ a_1, a_2, \dots, a_n $ 和一个整数 $ k $ ，你需要计算一个新数组 $ b_1, b_2, \dots, b_n $ ，其中 - $ b_1 = (\binom{1}{k} \cdot a_1) \bmod 998244353 $ ； - $ b_2 = (\binom{2}{k} \cdot a_1 + \binom{1}{k} \cdot a_2) \bmod 998244353 $ ； - $ b_3 = (\binom{3}{k} \cdot a_1 + \binom{2}{k} \cdot a_2 + \binom{1}{k} \cdot a_3) \bmod 998244353 $ ，依此类推。 具体而言，$ b_i = (\sum\limits_{j=1}^{i} \binom{i - j + 1}{k} \cdot a_j) \bmod 998244353 $ 。 注意，数组以一种修改的方式给出，你也需要以一种修改的方式输出。 ## 输入格式 输入的第一行包含六个整数 $ n $ ， $ a_1 $ ， $ x $ ， $ y $ ， $ m $ 和 $ k $ （ $ 1 \le n \le 10^7 $ ； $ 0 \le a_1, x, y < m $ ； $ 2 \le m \le 998244353 $ ； $ 1 \le k \le 5 $ ）。 数组 $ [a_1, a_2, \dots, a_n] $ 的生成方式如下： - 输入给定了 $ a_1 $ ； - 对于 $ 2 \le i \le n $ ， $ a_i = (a_{i-1} \cdot x + y) \bmod m $ 。 ## 输出格式 由于输出最多可能有 $ 10^7 $ 个整数，可能会导致速度过慢，因此你需要进行以下处理： 设 $ c_i = b_i \cdot i $ （不在乘法后取模 $ 998244353 $ ）。输出整数 $ c_1 \oplus c_2 \oplus \dots \oplus c_n $ ，其中 $ \oplus $ 表示按位异或运算。 ## 样例 #1 ### 输入样例 #1 ``` 5 8 2 3 100 2 ``` ### 输出样例 #1 ``` 1283 ```Output
这是一个组合数学问题。给定一个数组 $a_1, a_2, \dots, a_n$ 和一个整数 $k$，要求计算一个新的数组 $b_1, b_2, \dots, b_n$，其中 $b_i$ 的值是根据给定的数组 $a$ 和整数 $k$ 通过组合数计算得出的。具体地，$b_i$ 的计算公式为 $b_i = \left(\sum_{j=1}^{i} \binom{i - j + 1}{k} \cdot a_j\right) \bmod 998244353$。输入的数组 $a$ 是按照特定规则生成的，输出的数组 $b$ 也需要按照特定规则输出。
输入数据格式：
输入只有一行，包含六个整数 $n, a_1, x, y, m, k$，分别表示数组 $a$ 的长度，数组的第一个元素，以及生成数组 $a$ 的参数。其中 $1 \le n \le 10^7$，$0 \le a_1, x, y < m$，$2 \le m \le 998244353$，$1 \le k \le 5$。
输出数据格式：
由于直接输出多达 $10^7$ 个整数可能太慢，因此需要按照以下规则输出：定义 $c_i = b_i \cdot i$（乘法后不取模 $998244353$），输出 $c_1 \oplus c_2 \oplus \dots \oplus c_n$ 的值，其中 $\oplus$ 表示按位异或运算符。题目大意： 这是一个组合数学问题。给定一个数组 $a_1, a_2, \dots, a_n$ 和一个整数 $k$，要求计算一个新的数组 $b_1, b_2, \dots, b_n$，其中 $b_i$ 的值是根据给定的数组 $a$ 和整数 $k$ 通过组合数计算得出的。具体地，$b_i$ 的计算公式为 $b_i = \left(\sum_{j=1}^{i} \binom{i - j + 1}{k} \cdot a_j\right) \bmod 998244353$。输入的数组 $a$ 是按照特定规则生成的，输出的数组 $b$ 也需要按照特定规则输出。 输入数据格式： 输入只有一行，包含六个整数 $n, a_1, x, y, m, k$，分别表示数组 $a$ 的长度，数组的第一个元素，以及生成数组 $a$ 的参数。其中 $1 \le n \le 10^7$，$0 \le a_1, x, y < m$，$2 \le m \le 998244353$，$1 \le k \le 5$。 输出数据格式： 由于直接输出多达 $10^7$ 个整数可能太慢，因此需要按照以下规则输出：定义 $c_i = b_i \cdot i$（乘法后不取模 $998244353$），输出 $c_1 \oplus c_2 \oplus \dots \oplus c_n$ 的值，其中 $\oplus$ 表示按位异或运算符。