思路:首先考虑t=1的情况,t等于1,那么所有位置的颜色相同,我们不用考虑概率的问题,那么,k+d*x在模d下都相等,我们考虑预处理一个数组s[i][j],代表d为i,起始位置为j的等差数列的和,这个可以证明,当模小于等于sqrt(n)的时候可以完美解决,时间复杂度为N^1.5,对于d大于sqrt(n)的情况,只需要暴力枚举就可以了。
再考虑t>=2的情况,我们选的颜色一定是颜色数最少的那个,颜色数最少的颜色的期望绝对是最小的,然后,我们分k的左边和k的右边进行计算,我们这里称呼k+d*x的位置,叫做关键位置,假设p[i]为i到k这一段上所有的关键位置全部都是同一个颜色的概率,那么转移,就是p[i+k]=p[i]*(x)/(n-1-x),x为最少的颜色个数。我们可以发现,x<(n-1)/2,p[i]是随指数级衰减的,那么我们只需要枚举一小段,当p[i]<eps时,那么它对答案就几乎没有影响了。
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
int block,n,m;
int s[][],a[];
const double eps=1e-;
int read(){
int t=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
void init(){
n=read();m=read();
for (int i=;i<=n;i++) a[i]=read();
block=ceil(sqrt(n))+0.1;
for (int i=;i<=block;i++)
for (int j=;j<=i;j++)
for (int k=j;k<=n;k+=i)
s[i][j]+=a[k];
}
void modify(int x,int y){
int T=y-a[x];
for (int i=;i<=block;i++)
s[i][(x-)%i+]+=T;
a[x]=y;
}
double deal(int k,int d){
if (d<=block) return s[d][(k-)%d+];
double res=;
for (int i=(k-)%d+;i<=n;i+=d)
res+=(double)a[i];
return res;
}
void solve(){
while (m--){
int opt=read();
if (opt==){
int x=read(),y=read();
modify(x,y);continue;
}
int num=0x7fffffff,t,k,d;
t=read();k=read();d=read();for (int i=;i<=t;i++){int l=read();num=std::min(num,l);}
if (t==) {printf("%.4f\n",deal(k,d));continue;}
double ans=(double)a[k],p=;
int N=num;
for (int i=k+d,Num=n-;i<=n&&num>;i+=d,Num--,num--){
p=p*num/Num;ans+=p*a[i];
if (p<eps&&n>=) break;
}
num=N;p=;
for (int i=k-d,Num=n-;i>=&&num>;i-=d,Num--,num--){
p=p*num/Num;ans+=p*a[i];
if (p<eps&&n>=) break;
}
printf("%.4f\n",ans);
}
}
int main(){
init();
solve();
}