题目大意
有n个鲨鱼围成一圈,每个鲨鱼有一个写着数字的花,第i个鲨鱼的数字在[ l i , r i l_i,r_i li,ri]区间等概率选取,如果有相邻的两个鲨鱼数字的乘积是p的倍数,那Wet Shark就会给他们每人1000元。
分析
样本空间的大小为 S = ∏ i = 1 n ( r i − l i + 1 ) S=\prod_{i=1}^{n}(r_i-l_i+1) S=i=1∏n(ri−li+1)
每种情况是等概率出现的,只需要将所有情况的Wet Shark需要付的钱加起来除以S即可。
然而,显然直接不能这样做,我们考虑优化。
令第i只鲨鱼的取值中有 n p i np_i npi个数字被p整除。
n p i = ⌊ r i p ⌋ − ⌊ l i − 1 p ⌋ np_i=\lfloor\frac{r_i}{p}\rfloor-\lfloor\frac{l_i-1}{p}\rfloor npi=⌊pri⌋−⌊pli−1⌋
考虑第i只和i+1只鲨鱼,如果第i只鲨鱼的数字整除p的,那无论第i+1只鲨鱼取什么数字,积都可以被整除。
如果第i只鲨鱼的数字不能被p整除,那么只有当第i+1只鲨鱼取质数时积才能被p整除。
也就是这两只鲨鱼对答案的贡献 G i = 2000 ∗ ( n p i ∗ ( r i + 1 − l i + 1 + 1 ) + ( r i − l i + 1 − n p i ) ∗ n p i + 1 ) ∗ ∏ j = 1 且 j ≠ i , i + 1 n ( r j − l j + 1 ) S = 2000 ∗ ( n p i ∗ ( r i + 1 − l i + 1 + 1 ) + ( r i − l i + 1 − n p i ) ∗ n p i + 1 ) ∗ ∏ j = 1 且 j ≠ i , i + 1 n ( r j − l j + 1 ) ∏ j = 1 n ( r j − l j + 1 ) = 2000 ∗ ( n p i ∗ ( r i + 1 − l i + 1 + 1 ) + ( r i − l i + 1 − n p i ) ∗ n p i + 1 ) ( r i − l i + 1 ) ∗ ( r i + 1 − l i + 1 + 1 ) G_i=\frac{2000*(np_i*(r_{i+1}-l_{i+1}+1)+(r_i-l_i+1-np_i)*np_{i+1})*\prod_{j=1且j\neq i,i+1}^{n}(r_j-l_j+1)}{S}\\=\frac{2000*(np_i*(r_{i+1}-l_{i+1}+1)+(r_i-l_i+1-np_i)*np_{i+1})*\prod_{j=1且j\neq i,i+1}^{n}(r_j-l_j+1)}{\prod_{j=1}^{n}(r_j-l_j+1)}\\=\frac{2000*(np_i*(r_{i+1}-l_{i+1}+1)+(r_i-l_i+1-np_i)*np_{i+1})}{(r_i-l_i+1)*(r_{i+1}-l_{i+1}+1)} Gi=S2000∗(npi∗(ri+1−li+1+1)+(ri−li+1−npi)∗npi+1)∗∏j=1且j̸=i,i+1n(rj−lj+1)=∏j=1n(rj−lj+1)2000∗(npi∗(ri+1−li+1+1)+(ri−li+1−npi)∗npi+1)∗∏j=1且j̸=i,i+1n(rj−lj+1)=(ri−li+1)∗(ri+1−li+1+1)2000∗(npi∗(ri+1−li+1+1)+(ri−li+1−npi)∗npi+1)
根据这个公式算出答案即可。
注意:1和n也是相邻的。
代码
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 100000
int n,p,l[MAXN+10],r[MAXN+10],np[MAXN+10];
double ans;
void Read(int &x){
char c;
while(c=getchar(),c!=EOF)
if(c>='0'&&c<='9'){
x=c-'0';
while(c=getchar(),c>='0'&&c<='9')
x=x*10+c-'0';
ungetc(c,stdin);
return;
}
}
void read(){
Read(n),Read(p);
for(int i=1;i<=n;i++){
Read(l[i]),Read(r[i]);
np[i]=r[i]/p-(l[i]-1)/p;
}
}
void solve(){
int i;
for(i=1;i<=n;i++)
ans+=(1.0*np[i]*(r[i%n+1]-l[i%n+1]+1)+1.0*(r[i]-l[i]+1-np[i])*np[i%n+1])/(r[i]-l[i]+1)*2000/(r[i%n+1]-l[i%n+1]+1);
}
int main()
{
read();
solve();
printf("%.7lf",ans);
}