Combinatorics Problem
题意翻译
# 组合数学问题
## 题目描述
回顾一下二项式系数 $ \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
```
题目描述
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.
输入输出格式
输入格式
The 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.
输入输出样例
输入样例 #1
5 8 2 3 100 2
输出样例 #1
1283