#1966. 组合数求和
组合数求和
组合数求和
题目描述
标题: 组合数求和 - Problem - QOJ.ac
#8459. 组合数求和
The problem was used in the following contests:
定义 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 = {n!m!⋅(n−m)!,0≤m≤n0,otherwise。xor 表示异或和。
输入格式
一行四个整数 n, m, d, M,由空格隔开。
输出格式
一行一个整数表示答案。
样例数据
样例输入
3 2 3 998244353
样例输出
10
样例解释
f(0) ≡ C00 + C30 + C60 ≡ 1 + 1 + 1 ≡ 3(mod998244353)
f(1) ≡ C01 + C31 + C61 ≡ 0 + 3 + 6 ≡ 9(mod998244353)
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 无
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3 2 3 998244353
10