NOI模拟 奥义商店【分块+概率dp】

题目描述：

解题思路：

#include<bits/stdc++.h> #define ll long long using namespace std; int getint() { int i=0,f=1;char c; for(c=getchar();(c!='-')&&(c<'0'||c>'9');c=getchar()); if(c=='-')c=getchar(),f=-1; for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0'; return i*f; } const int N=100005,S=300; int n,m,a[N],sum[S][S]; double p[S]; int query1() { int res=0,k=getint(),d=getint();getint(); if(d<S)return sum[d][k%d]; else { for(int i=k;i>=1;i-=d)res+=a[i]; for(int i=k+d;i<=n;i+=d)res+=a[i]; } return res; } double query2(int t) { int k=getint(),d=getint(),c=N; for(int i=1;i<=t;i++)c=min(c,getint()); p[0]=1;int L=min(100,c); for(int i=1;i<=L;i++)p[i]=p[i-1]*(c-i+1)/(n-i); double res=0; for(int i=0;i<=L&&k-i*d>=1;i++)res+=a[k-i*d]*p[i]; for(int i=1;i<=L&&k+i*d<=n;i++)res+=a[k+i*d]*p[i]; return res; } int main() { freopen("lzz.in","r",stdin); freopen("lzz.out","w",stdout); n=getint(),m=getint(); for(int i=1;i<=n;i++) { a[i]=getint(); for(int j=1;j<S;j++)sum[j][i%j]+=a[i]; } while(m--) { int op=getint(); if(op==1) { int i=getint(),x=getint(); for(int j=1;j<S;j++)sum[j][i%j]+=x-a[i]; a[i]=x; } else { int t=getint(); if(t==1)printf("%0.4lf\n",(double)query1()); else printf("%0.4lf\n",query2(t)); } } return 0; }