#PQJ313x8459. QOJ 313_8459

    ID: 2908 传统题 3000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2019 互测数学组合数学

QOJ 313_8459

标题: 组合数求和 - Problem - QOJ.ac

#8459. 组合数求和

Statistics

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 无