T16110 小象涂色

题目描述

小象喜欢为箱子涂色。小象现在有 c 种颜色,编号为 0~c-1;还有 n 个箱子,编号

为 1~n,最开始每个箱子的颜色为 1。小象涂色时喜欢遵循灵感:它将箱子按编号排成

一排,每次涂色时,它随机选择[L,R]这个区间里的一些箱子(不选看做选 0 个),为

之涂上随机一种颜色。若一个颜色为 a 的箱子被涂上 b 色,那么这个箱子的颜色会变成

(a*b)mod c。请问在 k 次涂色后,所有箱子颜色的编号和期望为多少?

输入输出格式

输入格式:

第一行为 T,表示有 T 组测试数据。

对于每组数据,第一行为三个整数 n,c,k。

接下来 k 行,每行两个整数 Li,Ri,表示第 i 个操作的 L 和 R。

输出格式:

对于每组测试数据,输出所有箱子颜色编号和的期望值,结果保留 9 位小数

输入输出样例

输入样例#1: 复制
输出样例#1: 复制

说明

40%的数据 1 <= T <= 5,1 <= n, k <= 15,2 <= c <= 20

100%的数据满足 1 <= T <= 10,1 <= n, k <= 50,2 <= c <= 100,1 <= Li <= Ri <= n

发现每个点在改变了k次的情况是可以预处理搞出来了。

就预处理一遍,然后统计一下就搞定了。

c++代码如下:

 

 

4 + 6 =