#PQJ1401x7649. QOJ 1401_7649
QOJ 1401_7649
标题: 序列 - Problem - QOJ.ac
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 都有梯度。