首页 > 代码库 > 【推导】【数学期望】Gym - 101237D - Short Enough Task
【推导】【数学期望】Gym - 101237D - Short Enough Task
按照回文子串的奇偶分类讨论，分别计算其对答案的贡献，然后奇偶分别进行求和。
推导出来，化简一下……发现奇数也好，偶数也好，都可以拆成一个等比数列求和，以及一个可以错位相减的数列求和。
然后用高中数学知识搞一下就行了。
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
int N;
double K;
double Quick_Pow(double x,int p){
if(!p){
return 1;
}
double ans=Quick_Pow(x,p>>1);
ans=ans*ans;
if(p&1){
ans=ans*x;
}
return ans;
}
int main(){
// freopen("c.in","r ",stdin);
while(scanf("%d%lf",&N,&K)!=EOF){
if(K==1){
cout<<(ll)(N+1)*(ll)N/2ll<<endl;
}
else{
double a=(double)(2+N)*(1-Quick_Pow(1/K,(N+1)/2))/(1-(1/K));
double b=-2.0*(1-Quick_Pow(1/K,(N+1)/2))/(1-1/K)/(1-1/K);
double c=2.0*(double)((N+1)/2)/Quick_Pow(K,(N+1)/2)/(1-1/K);
// double d=((double)(N+1)-2.0*(1-Quick_Pow(1/K,N/2+1))/(1-1/K))/(K+1);
// double d=((double)(N+1)/K-2.0*(1-Quick_Pow(1/K,N/2))/(K-1)-((double)(N+2)-2*(N/2))/Quick_Pow(K,N/2+1))/(1-1/K);
double d=(double)(N+1)*(1-Quick_Pow(1/K,N/2))/K/(1-1/K);
double e=-2.0*(1-Quick_Pow(1/K,N/2))/K/(1-1/K)/(1-1/K);
double f=2.0*(double)(N/2)/Quick_Pow(K,N/2+1)/(1-1/K);
printf("%.10f\n",a+b+c+d+e+f);
}
}
return 0;
}
【推导】【数学期望】Gym - 101237D - Short Enough Task
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。