商城网站类建设哪家好,网站开发浏览器分辨率,淘宝客如何做淘宝客网站,鞋子 东莞网站建设2018 ACM-ICPC World Finals Problem D.Gem Island
Solution
其实就是求x1x2⋯xnnd,xi∈[1,d1]x_1x_2\dots x_nnd,x_i\in[1,d1]x1x2⋯xnnd,xi∈[1,d1]的前rrr大的xix_ixi的和的期望#xff0c;可以发现每一种不同的序列{xi}\{x_i\}{xi}的出现概率都是一个定值x2⋯xnnd,xi∈[1,d1]x_1x_2\dots x_nnd,x_i\in[1,d1]x1x2⋯xnnd,xi∈[1,d1]的前rrr大的xix_ixi的和的期望可以发现每一种不同的序列{xi}\{x_i\}{xi}的出现概率都是一个定值1(nd−1d)\frac{1}{\binom{nd-1}{d}}(dnd−1)1
因此我们只需要求出所有方案的前rrr大的xix_ixi的和再乘以这个概率即可。 于是我们沿用loj6077的dpdpdp做法注意这里我们只考虑分裂产生的贡献因此xix_ixi的范围为[0,d][0,d][0,d]求x1x2⋯xndx_1x_2\dots x_ndx1x2⋯xnd的贡献和最后的答案需要再加上rrr令fi,jf_{i,j}fi,j表示iii个人分裂jjj次的前rrr大宝石个数和。
考虑这个序列中有kkk个大于000的数它们都是被加若干个111过来的有(ik)\binom{i}{k}(ki)种方案选出这些数本次分裂产生的贡献和为min(k,r)∗(j−k(k−1)k−1)min(k,r)*\binom{j-k(k-1)}{k-1}min(k,r)∗(k−1j−k(k−1))而之后的贡献为fk,j−kf_{k,j-k}fk,j−k因此有 fi,j∑k(ik)(min(k,r)(j−1k−1)fk,j−k)f_{i,j}\sum_k \binom{i}{k}(min(k,r)\binom{j-1}{k-1}f_{k,j-k})fi,jk∑(ki)(min(k,r)(k−1j−1)fk,j−k)
时间复杂度为O(nd⋅min(n,d))O(nd\cdot min(n,d))O(nd⋅min(n,d))。
事实上本题还有O(d2nd)O(d^2nd)O(d2nd)求出所有rrr的答案的容斥做法但是比较复杂且精度丢失比较严重这里不作描述。
Code
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods1e97;
const int MAXN1005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
lod f[MAXN][MAXN],C[MAXN][MAXN];
void Init(int n)
{for (int i0;in;i) C[i][i]C[i][0]1;for (int i2;in;i)for (int j1;ji;j) C[i][j]C[i-1][j-1]C[i-1][j];
}
signed main()
{int nread(),dread(),rread(); Init(nd);for (int i1;in;i)for (int j0;jd;j)for (int k0;kikj;k) f[i][j]C[i][k]*((j?C[j-1][k-1]:0)*min(k,r)f[k][j-k]);printf(%.11lf\n,(double)(f[n][d]/C[nd-1][d]r));return 0;
}
