ACOI-11月月赛 T7 哈

ACOI-11月月赛 T7 哈

暂无测试数据。

题目背景

\(\color{brown}{\sf 2024yuhongyi}\) 遇到了一个问题)~~没有人会遇到这种问题。~~

他不会,所以想请你帮忙和他一起哈哈哈。

题目描述

给定一个长度为 \(n\) 的**数列** \(a\)。

每次询问给定一个**区间** \([l,r]\),和一个**质数** \(p\)。

请你求出:

\[\prod _{i=l}^r[\frac{(\sum_{j=l}^ia_jp)!}{\prod_{j=l}^ip^{a_j}(\sum_{j=l}^ia_j)!}\bmod p]\bmod (10^9+7)\]

输入格式

第一行,两个数,代表 \(n\) 和 \(q\)。

接下来 \(q\) 行,每行三个数,对应每次询问的 l r p

输出格式

共 \(m\) 行,每行一个数,代表每次询问的答案。

样例 #1

样例输入 #1

5 5
1 5 3 5 2
1 5 2
2 4 3
3 5 11
1 1 2
1 5 10007

样例输出 #1

1
4
10
1
100120036

样例 #2

样例输入 #2

50 10
534 6534 324 789 79 789 798 7984 43 2 534 6534 324 789 79 789 798 7984 43 2 534 6534 324 789 79 789 798 7984 43 2 534 6534 324 789 79 789 798 7984 43 2 534 6534 324 789 79 789 798 7984 43 2
2 34 2
5 6 11
1 49 17
2 50 97
45 48 7
3 3 2
1 50 10007
30 40 10007
1 10 10007
5 50 5

样例输出 #2

1
10
496641140
291552291
6
1
356715574
538473149
538473149
383381198

提示

数据范围:

子任务 \(n \le\) \(q \le\) 分值
\(1\) \(10\) \(10\) \(20\)
\(2\) \(10^4\) \(10^3\) \(30\)
\(3\) \(10^6\) \(10^3\) \(15\)
\(4\) \(10^6\) \(2 \times 10^5\) \(35\)

因为这是,所以请你忽略以上分值。

对所有数据都有:

\(1 \le n \le 10^6,1 \le q \le 2 \times 10^5,1 \le a_i \le 10^9,1 \le l \le r \le n,2 \le p \le 10^6\)。

其中 \(p\) 总是质数。

信息

ID
1047
难度
(无)
分类
(无)
标签
(无)
递交数
0
已通过
0
通过率
?
上传者

相关

在下列训练计划中:

“你今天AC了吗”团队原创