- 本题为简单题(虽然当时还是没做出来0.0)。
2.题目大意为:有n个数,其范围都为[0,1],进行m次操作(二分之一的可能去掉最大数,二分之一的可能去掉最小数),求m次操作后剩下数的和的期望值。
3.当时我是全部进行期望间的运算,得到了(n-m)/2这个答案(正确答案也确实如此).但为什么还是爆零了呢?
4.这又要谈到乘法逆元这一知识点。[https://blog.csdn.net/qq_37656398/article/details/81434277]
5.因为此题对1e9+7取模,所以我们不能直接除以2,我们应求出2的乘法逆元,然后将其转化为乘法。
6.关于期望的计算:
我是先计算一个数的期望值,因为我们可以把0到1分为n份(默认n为奇数),所以对于期望值,我们可以得到期望=1/n*1/2+1/n*(0+0.00...1+0.00...2+...+0.99...9+0.99...8+1)=1/2n+1/n*1*(n-1)/2=1/2;
在对一次操作的对于的期望值进行计算,期望值=1/2*1/n*(0+0.00...1+...+0.99...9+1)+1/2*1/n*(0+0.00..1+...+0.99...9+1)=1/2n*1*n=1/2;
所以进行m次操作的期望值=n*1/2-m*1/2=(n-m)/2;
7.对于算法的一点看法: 我是用快速幂的方法求出乘法逆元,因此我是在循环外面先求出一个乘法逆元,再带进去,减少不必要的操作。
8.代码:
#include
#include
using namespace std;
long long int mod=1e9+7;
long long int power(long long int a,long long int b){
if(b==0)
return 1;
else if(b%2==1)
return power(a,b-1)*a%mod;
else{
long long int temp=power(a,b/2)%mod;
return temp*temp%mod;
}
}
int main(){
int n,m,t;
long long int mid;
mid=power(2,mod-2);
cin>>t;
while(t>0){
scanf("%d %d",&n,&m);
cout<<(n-m)*mid%mod<<endl;
t--;
}
printf("%lld\n",mod);
printf("%lld",mid);
return 0;
}
9.第一次写题解,希望各位大神多多指点^_^.