#3075. 「2019 集训队互测 Day 3」组合数求和

内存限制:256 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: cz_xuyixuan

题目描述

定义 f(j)\ \equiv\ \sum_{i=0}^{n-1}\ C_{i\cdot d}^{j}\ (\bmod\ M),\ 0\ \leq\ f(j)\ <\ M ,其中 n,\ d,\ M 为给定值。

现在给定 m ,输出 f(0)\ \mathrm{xor}\ f(1)\ \mathrm{xor}\ f(2)\ \mathrm{xor}\ \cdots\ \mathrm{xor}\ f(m\ -\ 1) 的值。

其中 C_{n}^{m} 为组合数 n m ,即 C_{n}^{m}\ =\ \begin{cases}\frac{n!}{m!\cdot (n-m)!}&, 0\leq m\leq n \cr 0&, \text{otherwise}\end{cases} \mathrm{xor} 表示异或和。

输入格式

一行四个整数 n,\ m,\ d,\ M ,由空格隔开。

输出格式

一行一个整数表示答案。

样例

样例输入一

3 2 3 998244353

样例输出一

10

样例一解释

f(0)\ \equiv\ C_0^0\ +\ C_3^0\ +\ C_6^0\ \equiv\ 1\ +\ 1\ +\ 1\ \equiv\ 3\ (\bmod\ 998244353)

f(1)\ \equiv\ C_0^1\ +\ C_3^1\ +\ C_6^1\ \equiv\ 0\ +\ 3\ +\ 6\ \equiv\ 9\ (\bmod\ 998244353)

f(0)\ \mathrm{xor}\ f(1)\ =\ 3\ \mathrm{xor}\ 9\ =\ 10

数据范围与提示

本题采用捆绑测试。

对于所有测试包均满足 1\ \leq\ d\ \leq\ 100,\ 1\ \leq\ m\cdot d\ \leq\ 3\times 10^6,\ 1\ \leq\ n\cdot d\ \leq\ 10^9,\ 10^8\ \leq\ M\ \leq\ 10^9

测试包编号 测试包分值 其它约定
1 4 n\cdot d,\ m\ \leq\ 2000
2 10 m\ \leq\ 400
3 6 m\ \leq\ 8000,\ M\ =\ 998244353
4 6 m\ \leq\ 8000
5 7 d\ =\ 1
6 22 \gcd(d,\ M)\ =\ 1
7 7 d\ =\ 2
8 7 d\ =\ 4
9 8 d 为质数
10 23