#P13058. [AGC052C] Nondivisible Prefix Sums

    ID: 12242 传统题 1000ms 256MiB 尝试: 49 已通过: 11 难度: 9 上传者: 标签>CF2600动态规划组合数学数论数学计数DP模运算

[AGC052C] Nondivisible Prefix Sums

题目描述

给定一个素数 PP,这是你讨厌的数字。

对于一个整数序列 A1, A2, …, ANA_1,\ A_2,\ \dots,\ A_N,如果可以重新排列这些元素,使得任意前缀和都不能被 PP 整除(即,重新排列后,对于所有 1≤i≤N1 \le i \le N,都不存在 A1+A2+⋯+Ai≡0(modP)A_1 + A_2 + \dots + A_i \equiv 0 \pmod{P}),那么称这个序列为好序列。

长度为 NN 的整数序列,每个元素都在 11 到 P−1P-1 之间(包含 11 和 P−1P-1),这样的序列一共有 (P−1)N(P-1)^N 种。请问其中有多少个好序列。

由于答案可能非常大,请输出其对 998244353998244353 取模的结果。

输入格式

输入从标准输入中给出,格式如下:

NN PP

输出格式

输出好序列的个数对 998244353998244353 取模的结果。

输入输出样例 #1

输入 #1

2 5

输出 #1

12

输入输出样例 #2

输入 #2

4 3

输出 #2

8

输入输出样例 #3

输入 #3

5000 99999989

输出 #3

51699346

输入输出样例 #4

输入 #4

2021 307

输出 #4

644635349

说明/提示

限制条件

  • 1≤N≤50001 \le N \le 5000
  • 2≤P≤1082 \le P \le 10^8
  • PP 是素数。

样例解释 1

好序列有 [1, 1][1,\ 1],[1, 2][1,\ 2],[1, 3][1,\ 3],[2, 1][2,\ 1],[2, 2][2,\ 2],[2, 4][2,\ 4],[3, 1][3,\ 1],[3, 3][3,\ 3],[3, 4][3,\ 4],[4, 2][4,\ 2],[4, 3][4,\ 3],[4, 4][4,\ 4] 共 1212 种。

样例解释 2

好序列有 [1, 1, 1, 2][1,\ 1,\ 1,\ 2],[1, 1, 2, 1][1,\ 1,\ 2,\ 1],[1, 2, 1, 1][1,\ 2,\ 1,\ 1],[2, 1, 1, 1][2,\ 1,\ 1,\ 1],[2, 2, 2, 1][2,\ 2,\ 2,\ 1],[2, 2, 1, 2][2,\ 2,\ 1,\ 2],[2, 1, 2, 2][2,\ 1,\ 2,\ 2],[1, 2, 2, 2][1,\ 2,\ 2,\ 2] 共 88 种。