入门BZOJ3003 [Noi2016十连测第一场]奥义商店

题面在这里

​

考虑从k开始，向两边的每个数出现的概率

\(a_{k-i\cdot d}\)对应的概率为\(\Pi_{j=1}^i \frac {m-j+1}{n-j}\)

这个东西很快就会比精度还小，所以最多算500项就够了

​

示例程序：

#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn=100005;
const double eps=1e-6;
int n,q;
double v[maxn],f[105][maxn];
int main(){
	scanf("%d%d",&n,&q);
	for (int i=1;i<=n;i++){
		scanf("%lf",&v[i]);
		for (int j=1;j<=100;j++) f[j][i%j]+=v[i];
	}
	while (q--){
		int c;scanf("%d",&c);
		if (c==1){
			int x,w;scanf("%d%d",&x,&w);
			for (int i=1;i<=100;i++) f[i][x%i]+=w-v[x];
			v[x]=w;
		}else{
			int t,k,d;scanf("%d%d%d",&t,&k,&d);
			if (t==1){
				int x;scanf("%d",&x);
				if (d<=100) printf("%.6lf\n",f[d][k%d]);else{
					double ans=v[k];
					for (int i=k+d;i<=n;i+=d) ans+=v[i];
					for (int i=k-d;i>=1;i-=d) ans+=v[i];
					printf("%.6lf\n",ans);
				}
			}else{
				int m=2e9,x;
				double ans=v[k],rate=1;
				while (t--) scanf("%d",&x),m=min(m,x);
				for (int i=1;i<=500&&k+i*d<=n;i++) rate*=1.0*(m-i+1)/(n-i),ans+=1.0*v[k+i*d]*rate;
				rate=1;
				for (int i=1;i<=500&&k-i*d>=1;i++) rate*=1.0*(m-i+1)/(n-i),ans+=1.0*v[k-i*d]*rate;
				printf("%.6lf\n",ans);
			}
		}
	}
	return 0;
}