## 【BZOJ 4318】OSU!

### 解题报告

$E_{(i,x^2)}，E_{(i,x)}$分别表示$x^2,x$的期望

$E_{(i,x^3)}=p_i \times E_{(i-1,(x+1)^3)}$
$E_{(i,x^2)}=p_i \times E_{(i-1,(x+1)^2)}$
$E_{(i,x)}=p_i \times (E_{(i-1,x)} + 1)$

$E_{(i,x^3)}=p_i \times (E_{(i-1,x^3)} + 3E_{(i-1,x^2)} + 3E_{(i-1,x)} + 1)$
$E_{(i,x^2)}=p_i \times (E_{(i-1,x^2)} + 2E_{(i-1,x)} + 1)$

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

int main() {
double e1=0,e2=0,e3=0,ans=0,p;
for (int i=1;i<=n;i++) {
scanf("%lf",&p);
ans += e3 * (1 - p);
e3 = p * (e3 + 3 * e2 + 3 * e1 + 1);
e2 = p * (e2 + 2 * e1 + 1);
e1 = p * (e1 + 1);
}
printf("%.1lf\n",ans+e3);
return 0;
}


## 【HDU 4624】Endless Spin

### Code

#include<bits/stdc++.h>
#define LL long long
#define LDB __float128
using namespace std;

const int N = 51;
const int M = N * N;

int n,ww,pp;
LL f[2][N][M][2];
LDB ans;

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

int main() {
ans = ww = 0; pp = 1;
memset(f,0,sizeof(f));
f[pp][0][0][0] = 1;
for (int i=0;i<n;i++,ww^=1,pp^=1) {
memset(f[ww],0,sizeof(f[ww]));
for (int j=0;j<=i;j++) {
for (int k=i*i;~k;k--) {
for (int p=0;p<=1;p++) {
if (f[pp][j][k][p]) {
f[ww][0][k+j*(j+1)/2][p^(j&1)] += f[pp][j][k][p];
f[ww][j+1][k][p] += f[pp][j][k][p];
}
}
}
}
}
for (int j=0;j<=n;j++) {
for (int k=n*n;~k;k--) {
for (int p=0;p<=1;p++) {
if (!f[pp][j][k][p]) continue;
int v = k + j * (j + 1) / 2, t = p ^ (j & 1);
LDB tmp = ((v < n * (n + 1) / 2)? ((LDB)v / (n * (n + 1) / 2 - v)): 0);
if ((n-t)&1) ans += tmp * f[pp][j][k][p];
else ans -= tmp * f[pp][j][k][p];
}
}
}
ans += 1;
printf("%.15Lf\n",(long double)ans);
}
return 0;
}


## 【BZOJ 3566】[SHOI2014] 概率充电器

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 500009;
const int M = N << 1;

double up[N],down[N],cost[M],q[N],vout;

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline void AddEdge(int u, int v, int f) {
static int E = 1;
cost[E+1] = cost[E+2] = f / 100.0;
}

void DFS1(int w, int f) {
down[w] = 1 - q[w];
if (to[i] != f) {
DFS1(to[i], w);
down[w] *= down[to[i]] + (1 - down[to[i]]) * (1 - cost[i]);
}
}
}

void DFS2(int w, int f, double p) {
vout += 1 - (up[w] = down[w] * p);
if (to[i] != f) {
double tmp = p * down[w] / (down[to[i]] + (1 - down[to[i]]) * (1 - cost[i]));
DFS2(to[i], w, tmp + (1 - tmp) * (1 - cost[i]));
}
}
}

int main() {
for (int i=1,u,v;i<n;i++) {
}
for (int i=1;i<=n;i++) q[i] = read() / 100.0;
DFS1(1, 1);
DFS2(1, 1, 1);
printf("%.6lf\n",vout);
return 0;
}


## 【BZOJ 4008】[HNOI2015] 亚瑟王

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int n,r,d[250];
double f[250][150],p[250][150],ans[250];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

int main() {
memset(f,0,sizeof(f)); memset(ans,0,sizeof(ans));
for (int i=1;i<=n;i++) scanf("%lf%d",&p[i][0],&d[i]);
for (int i=1;i<=n;i++) {
p[i][1] = 1 - p[i][0];
for (int j=2;j<=r;j++) p[i][j] = p[i][j-1] * p[i][1];
}
f[1][r] = 1;
for (int i=1;i<=n;i++) {
for (int j=1;j<=r;j++) {
ans[i] += f[i][j] * (1 - p[i][j]);
f[i+1][j] += f[i][j] * p[i][j];
f[i+1][j-1] += f[i][j] * (1 - p[i][j]);
}
}
double vout = 0;
for (int i=1;i<=n;i++) vout += ans[i] * d[i];
printf("%.10lf\n",vout);
}
return 0;
}


## 【日常小测】随机游走

### 解题报告

$$f_u=\deg u + \sum\limits_{v \in son_u}{f_v}$$
$$g_u=\deg fa_u + \sum\limits_{v \in son_{fa_u},v \ne u}{f_v} + g_{fa_{fa_u}}$$

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int M = N << 1;

int in[N],dep[N],fa[N][20];
LL f[N],g[N],PreF[N],PreG[N];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline void AddEdge(int u, int v) {
static int E = 1; in[u]++; in[v]++;
}

inline int LCA(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
for (int i=19;~i;i--) if (dep[fa[u][i]]>=dep[v]) u = fa[u][i];
if (u == v) return u;
for (int i=19;~i;i--) if (fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
return fa[u][0];
}

void DFS1(int w, int anc) {
fa[w][0] = anc;	f[w] = in[w];
dep[w] = dep[anc] + 1;
if (to[i] != anc) {
DFS1(to[i], w);
f[w] += f[to[i]];
}
}
}

void DFS2(int w, int anc) {
PreF[w] = PreF[anc] + f[w];
PreG[w] = PreG[anc] + g[w];
if (to[i] != anc) {
g[to[i]] = f[w] - f[to[i]] + g[w];
DFS2(to[i], w);
}
}
}

int main() {
DFS1(1, 1);
DFS2(1, 1);
for (int j=1;j<20;j++) {
for (int i=1;i<=n;i++) {
fa[i][j] = fa[fa[i][j-1]][j-1];
}
}
for (int i=1,u,v,lca;i<=m;i++) {
printf("%lld\n",PreF[u]-PreF[lca]+PreG[v]-PreG[lca]);
}
return 0;
}


## 【BZOJ 1426】收集邮票

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdio>
#include<cmath>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 10000+9;

int n;
double f[N],g[N];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
return ret*f;
}

int main(){
n = read(); f[n] = g[n] = 0;
for (int i=n-1;~i;i--) f[i] = (double)n/(n-i) + f[i+1];
for (int i=n-1;~i;i--) g[i] = f[i]*n/(n-i) + g[i+1];
printf("%.2lf",g[0]);
return 0;
}


## 【POJ 2096】Collecting Bugs

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

const int MAXN = 1000+9;

int n,m;
double f[MAXN][MAXN];

int main(){
cin>>n>>m;
for (int i=n;~i;i--) for (int j=m;~j;j--) if (i != n || j != m)
f[i][j] = ((double)i*j+(f[i+1][j]+1)*(n-i)*j+(f[i][j+1]+1)*i*(m-j)+(f[i+1][j+1]+1)*(n-i)*(m-j))/(n*m-i*j);
printf("%.4lf\n",f[0][0]);
return 0;
}