首页 > 试题广场 >

序列查询

[编程题]序列查询
给你一个序列a，有m次，每次查询一个区间[l,r]。
这个区间内一共有2^(r-l+1)-1个非空子序列
一个子序列对答案的贡献是其去重后的和
求所有子序列的贡献的和%p
每次的p不一样

输入描述:
第一行两个数n,m
第二行n个数表示序列a
后面m行每行三个数l,r,p表示查询区间[l,r]，模数是p


输出描述:
对于每个查询输出一行一个数表示答案
示例1

输入

5 5
1 2 2 3 4
1 2 233333
2 3 333333
1 5 203
3 5 15
2 4 8

输出

6
6
176
6
0

说明

[1,2]中有3个子序列(1),(2),(1,2)，贡献分别为1,2,3
[2,3]中有3个子序列(2),(2),(2,2)，贡献分别为2,2,2
[1,5]中有31个子序列
(1),(2),(2),(3),(4),(1,2),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(2,3),(2,4),(3,4),(1,2,2),(1,2,3),(1,2,4),(1,2,3),(1,2,4),(1,3,4),(2,2,3),(2,2,4),(2,3,4),(2,3,4),(1,2,2,3),(1,2,2,4),(1,2,3,4),(1,2,3,4),(2,2,3,4),(1,2,2,3,4)
贡献为:1,2,2,3,4,3,3,4,5,2,5,6,5,6,7,3,6,7,6,7,8,5,6,9,9,6,7,10,10,9,10
[3,5]中有7个子序列
(2),(3),(4),(2,3),(2,4),(3,4),(2,3,4)
贡献为:2,3,4,5,6,7,9
[2,4]中有7个子序列
(2),(2),(3),(2,2),(2,3),(2,3),(2,2,3)
贡献为:2,2,3,2,5,5,5

备注:
对于100%的数据，有1 <= n , m , a[i] <= 100000 , 1 <= p <= 1000000000
算法知识视频讲解
开通博客

暂无题解

问题信息

莫队
上传者：牛客301599号
难度：
0条回答 30浏览

热门推荐

通过挑战的用户

查看代码

相关试题

序列查询

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号