题目描述
定义 f(j) ≡ ∑i=0n−1 Ci⋅dj (modM), 0 ≤ f(j) < M,其中 n, d, M 为给定值。
现在给定 m,输出 f(0) xor f(1) xor f(2) xor ⋯ xor f(m−1) 的值。
其中 Cnm 为组合数 n 选 m,即 Cnm = {m!⋅(n−m)!n!0,0≤m≤n,otherwise。xor 表示异或和。
输入格式
一行四个整数 n, m, d, M,由空格隔开。
输出格式
一行一个整数表示答案。
样例
3 2 3 998244353
10
f(0) ≡ C00 + C30 + C60 ≡ 1 + 1 + 1 ≡ 3 (mod 998244353)
f(1) ≡ C01 + C31 + C61 ≡ 0 + 3 + 6 ≡ 9 (mod 998244353)
f(0) xor f(1) = 3 xor 9 = 10
数据范围与提示
本题采用捆绑测试。
对于所有测试包均满足 1 ≤ d ≤ 100, 1 ≤ m⋅d ≤ 3×106, 1 ≤ n⋅d ≤ 109, 108 ≤ M ≤ 109。
测试包编号 |
测试包分值 |
其它约定 |
1 |
4 |
n⋅d, m ≤ 2000 |
2 |
10 |
m ≤ 400 |
3 |
6 |
m ≤ 8000, M = 998244353 |
4 |
6 |
m ≤ 8000 |
5 |
7 |
d = 1 |
6 |
22 |
gcd(d, M) = 1 |
7 |
7 |
d = 2 |
8 |
7 |
d = 4 |
9 |
8 |
d 为质数 |
10 |
23 |
无 |