#1912. 取球
取球
取球
题目描述
标题: 取球 - Problem - QOJ.ac
#10347. 取球
The problem was used in the following contests:
小A和小B玩一个游戏。小A找了一些数,把它们装进一个袋子里,然后随机拿出一个,让小B猜是多少。小B很快发现猜期望(即这些数的平均数)是最接近的,于是每次都猜期望。小A觉得有些无聊了,于是把游戏增强了,但是小B又很快地发现猜期望最好。
增强了许多次以后,游戏变成了这样:从2个袋子里各随机取出一个数,分别记作m、n,然后小A拿出m个球和n个袋子,将球都随机放进袋子中,然后再随机找出一个袋子,让小B猜里面有多少个球**(小B知道m和n分别是多少)**。现在小A有些好奇,如果小B每次都猜期望,那么猜的“偏差度”是多少呢?小A问你袋子里的实际球数减去小B猜的数的差的k次方的期望。
其实,如果设袋子里的实际球数为x,那么小A问你的东西叫做变量x的k阶中心矩,它的定义是E((x−E(x))k)。特别地,2阶中心矩就是方差。
输入格式
输入第一行包含3个正整数Nn,Nm和Nk,分别表示取n、m的袋子的数的种类数和询问个数。
接下来Nn行,每行包含两个正整数ni和numni,表示取n的袋子中有numni个ni。
接下来Nm行,每行包含两个正整数mi和nummi,表示取m的袋子中有nummi个mi。
接下来Nk行,每行包含一个正整数k,表示一次询问。
输出格式
可以证明,答案一定是有理数。共输出Nk行,每行一个整数,表示一次询问的答案模1000000007(109+7)的结果,即,设答案为a/b(a和b为互质的正整数),你输出的整数为x,则你需要保证b⋅x与a模1000000007同余且0≤x<1000000007。
样例数据
样例输入
1 1 2
3 1
2 1
2
3
样例输出
444444448
481481485
样例说明
设(a,b,c)表示3个袋子中的球数分别是a、b、c,对于第一个询问,(2,0,0), (0,2,0), (0,0,2)的概率都是1/9,方差都是8/9,(1,1,0), (1,0,1), (0,1,1)的概率都是2/9,方差都是2/9,所以方差的期望是1/9∗8/9∗3+2/9∗2/9∗3=4/9。444444448∗9与4模1000000007同余。
样例输入
2 2 2
3 2
2 1
3 2
2 1
2
3
样例输出
172839508
650205766
样例说明
对于第一个询问,有4/9的概率是3袋3球,方差的期望是2/3;有2/9的概率是2袋3球,方差的期望是3/4;有2/9的概率是3袋2球,方差的期望是4/9;有1/9的概率是2袋2球,方差的期望是1/2。所以所求等于4/9×2/3+2/9×3/4+2/9×4/9+1/9×1/2=50/81。172839508×81与50模1000000007 同余。
数据规模和约定
对于全部测试数据,ni,mi≤109,Nn≤5000,Nm,k,numni,nummi≤2000,Nk≤200。
测试点编号 k≤ ni,mi≤ Nn= Nm= Nk= 1 1 7 1 1 1 2 2 7 1 1 1 3 2 30 1 1 1 4 2 30 2 2 1 5 2 104 1 1 1 6 2 109 200 200 1 7 3 30 2 2 2 8 3 104 2 2 2 9 3 104 200 200 2 10 4 30 2 2 2 11 50 5×106 1 1 1 12 50 109 2000 50 50 13 50 109 50 2000 50 14 50 109 2000 2000 50 15 300 30 2 2 2 16 300 109 2 2 2 17 300 109 200 200 200 18 300 109 200 200 200 19 2000 109 2 2 2 20 2000 109 5000 2 2
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
1 1 2
3 1
2 1
2
3
444444448
481481485
样例 2
2 2 2
3 2
2 1
3 2
2 1
2
3
172839508
650205766