编程介的小学生
2019-03-30 10:01数字连乘的一个算法问题,循环的计算用C语言的程序设计的办法
Problem Description
There are N rooms in the palace of “Hou”. (Obviously Roba is the master!) There are Ai girls in the i-th room and their value of charm is 1, 2... Ai, respectively.
Roba will pick out one girl in one room (randomly). Obviously, only N girl could meet Roba in a single day! Every girl has her value of charm. Now Roba wants to know the number of grils whose value of charm is exactly x! So F(Girl_Selected, x) is defined as the number of grils whose value of charm is exactly x in Girl_Selected.
For example, when N = 3, and Roba pick out three grils whose value of charm is 2, 3, 2 respectively, that is to say, Girl_Selected = {2,3,2}, so F({2,3,2}, 2) = 2, F({2,3,2},3) = 1, F({2,3,2},1) = 0.
Now Roba has Q queries. Each query will be one of the following operations:
1 val : Output the sum of F(Girl_Selected _possible_way, val) for all possible combination. As we know, there must be
different ways for Roba to pick out the N grils in a single day! Since the answer may be huge, you should output the answer mod P.
2 pos val : rearrange room pos from ( Apos ) to val, which means Roba maybe sometimes Friends Old and New! After arrangement, val grils in room pos and their value of charm is 1,2,… val respectively ! Note that 1<=val<=109 and 0<=pos<N.
Input
The first line is an integer T indicates the number of the test cases. (T <= 40)
Each case begins with one line containing three integers N (1<=N<=105), P (2 <= P <= 109, P is a prime) and Q(1<= Q <= 105), representing the number of rooms of palace of “Hou”, the mod number and the number of queries respectively. Then one line contains N numbers, the i-th number indicating the initial Ai. In the next Q line, each line contains one operation fits the description. (1 <= Ai <= 109)
Output
Output one line for each type-1 query.
Sample Input
1
4 7 5
1 2 3 4
1 2
2 0 7
1 4
2 0 5
1 3
Sample Output
5
3
3
- 点赞
- 回答
- 收藏
- 复制链接分享
0条回答
为你推荐
- C语言 数据结构 舞伴配对问题
- c
- 数据结构与算法分析
- 1个回答
- 关于C语言数组的一个问题
- c
- 2个回答
- ,,,,,C语言填空题求解答
- 7个回答
- 关于c语言实现队列的算法,总会出现内存方面错误,求高人指明错误
- c
- 内存
- 算法
- 5个回答