#PQJ1401x7649. QOJ 1401_7649

    ID: 2598 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2023-2024 集训队互测动态规划数学

QOJ 1401_7649

标题: 序列 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

称一个序列 (a1,a2,⋯,an) 是避免 120 模式的,当且仅当不存在 1≤i<j<k≤n 使得 ak<ai<aj。

给定质数 P。q 次询问,每次给定 n,m,求有多少个长度为 n 的、值域在 [0,m] 内的整数序列 a 是避免 120 模式的,结果对 P 取模。

输入格式

第一行两个整数 P,q,表示模数和询问次数。

接下来 q 行,每行两个整数 n,m,表示一组询问。

输出格式

输出共 q 行,第 i 行表示第 i 次询问的答案对 P 取模的结果。

样例数据

见下发文件。

数据范围

对于全部数据,满足 108≤P≤109,1≤q≤8×104,1≤n≤100,0≤m≤109。

测试点编号n≤m≤1,216163,418185,6181097,820209,102010911∼1610010017∼20100109

测试点 11∼20 关于 n 和 q 都有梯度。