编程介的小学生 2017-11-02 02:36 采纳率: 20.5%
浏览 864
已采纳

How Many HouGong

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

  • 写回答

1条回答 默认 最新

报告相同问题?

悬赏问题

  • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
  • ¥15 ubuntu系统下挂载磁盘上执行./提示权限不够
  • ¥15 Arcgis相交分析无法绘制一个或多个图形
  • ¥15 关于#r语言#的问题:差异分析前数据准备,报错Error in data[, sampleName1] : subscript out of bounds请问怎么解决呀以下是全部代码:
  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
  • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
  • ¥30 3天&7天&&15天&销量如何统计同一行
  • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型