第 77 场 AtCoder Grand Contest
区间替换 2AI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)You are given a positive integer $N$ and a prime $P$.
给定一个正整数 $N$ 和一个素数 $P$。AI (CI翻译)
There is a sequence $A=(A_1,A_2,\ldots,A_N)$ of length $N$ where all elements are $0$.
有一个长度为 $N$ 的序列 $A=(A_1,A_2,\ldots,A_N)$，其中所有元素均为 0。AI (CI翻译)
You can repeat the following operation zero or more times.
你可以将以下操作执行任意次，也可以一次都不执行。AI (CI翻译)
- Choose a pair of integers
$(l, r)\ (1\leq l\leq r\leq N)$. Replace each of$A_l,A_{l+1},\ldots,A_r$with$\dfrac{r(r-1)}{2}+l$.
- 选择一对整数
$(l, r)\ (1\leq l\leq r\leq N)$。将$A_l,A_{l+1},\ldots,A_r$中的每个元素替换为$\dfrac{r(r-1)}{2}+l$。
Find the number, modulo $P$, of sequences that can be obtained as $A$ after performing operations.
求执行操作后能够得到的序列 $A$ 的数量。答案对 $P$ 取模。AI (CI翻译)
Constraints
约束条件
AI (CI翻译)$1\leq N\leq 5000$$P$is a prime satisfying$10^8\lt P\lt 10^9$.- All input values are integers.
$1\leq N\leq 5000$$P$是满足$10^8\lt P\lt 10^9$的素数。- 所有输入值均为整数。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format:
输入从标准输入给出，格式如下：AI (CI翻译)
N PN POutput
输出格式
AI (CI翻译)Output the answer.
输出答案。AI (CI翻译)
样例
Input #1
1 998244353
Output #1
2
The two possible sequences $A$ are $(0)$ and $(1)$.
Input #2
2 998244353
Output #2
7
The seven possible sequences $A$ are $(0,0),(0,3),(1,0),(1,2),(1,3),(2,2),(2,3)$.
Input #3
3 998244353
Output #3
38
Input #4
4 998244353
Output #4
282
Input #5
77 777777773
Output #5
112061248
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。