## 【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;
}


## 【Codeforces 749E】Inversions After Shuffle

### Code

#include<bits/stdc++.h>
#define LL long long
#define lowbit(x) ((x)&-(x))
using namespace std;

const int N = 100009;

int n, p[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;
}

class Fenwick_Tree{
double sum[N];
public:
inline void init() {
memset(sum, 0, sizeof(sum));
}
inline void modify(int p, int d = 1) {
for (int i = p; i <= n; i += lowbit(i)) {
sum[i] += d;
}
}
inline double query(int p) {
double ret = 0;
for (int i = p; i; i -= lowbit(i)) {
ret += sum[i];
}
return ret;
}
}BIT;

int main() {
for (int i = 1; i <= n; i++) {
}
double ans = 0, psm = 0;
for (int i = n; i; i--) {
ans += BIT.query(p[i]);
BIT.modify(p[i]);
}
ans *= n * (n + 1ll);
BIT.init();
for (int i = 1; i <= n; i++) {
LL t1 = BIT.query(p[i]);
LL t2 = i * (i - 1ll) / 2 - t1;
ans += (psm += t1 - t2);
BIT.modify(p[i], i);
}
printf("%.15lf\n", ans / n / (n + 1));
return 0;
}


## 【Codeforces 802L】Send the Fool Further! (hard)

### Code

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

const int N = 100009;
const int M = 200009;
const int MOD = 1000000007;

int n, head[N], nxt[M], to[M], cost[M];
int a[N], b[N], fa[N], d[N];

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;
}

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

inline int REV(int x) {
int ret = 1, t = MOD - 2;
for (; t; x = (LL)x * x % MOD, t >>= 1) {
if (t & 1) {
ret = (LL)ret * x % MOD;
}
}
return ret;
}

void solve(int w, int f) {
if (d[w] > 1) {
a[w] = -1;
for (int i = head[w]; i; i = nxt[i]) {
b[w] = (b[w] + (LL)cost[i] * REV(d[w])) % MOD;
if (to[i] != f) {
solve(to[i], w);
}
}
if (w != f) {
b[f] = (b[f] - (LL)b[w] * REV((LL)a[w] * d[f] % MOD)) % MOD;
a[f] = (a[f] - REV((LL)d[w] * d[f] % MOD) * (LL)REV(a[w])) % MOD;
}
}
}

int main() {
#ifdef DBG
freopen("11input.in", "r", stdin);
#endif
for (int i = 1; i < n; ++i) {
}
solve(1, 1);
int ans = (LL)b[1] * REV(MOD - a[1]) % MOD;
ans = (ans + MOD) % MOD;
cout<<ans<<endl;
return 0;
}


## 【TopCoder SRM712】AverageVarianceSubtree

### Code

long double 最后一个点被卡精度了，只能用__float128

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

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

class AverageVarianceSubtree {
__float128 ans,tot,val[N],s1[N][N],s2[N][N],s3[N][N],cnt[N][N];
public:
double average(vector<int> p, vector<int> weight) {
memset(s1,0,sizeof(s1)); memset(s2,0,sizeof(s2));
memset(s3,0,sizeof(s3)); memset(cnt,0,sizeof(cnt));

n = weight.size();
for (int i=1;i<=n;i++) val[i] = weight[i - 1];
for (int i=0;i<n-1;i++) AddEdge(i + 2, p[i] + 1);
DFS(1, 1);
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) {
ans += (s2[i][j] - s3[i][j] / j) / j;
tot += cnt[i][j];
}
}
return ans / tot;
}
private:
inline void AddEdge(int u, int v) {
}
void DFS(int w, int f) {
cnt[w][0] = cnt[w][1] = 1;
s1[w][1] = val[w];
s2[w][1] = s3[w][1] = val[w] * val[w];
if (to[i] != f) {
DFS(to[i], w);
for (int t=n;t;t--) {
for (int a=1,b;b=t-a,a<t;a++) {
s3[w][t] += s3[w][a] * cnt[to[i]][b] + s3[to[i]][b] * cnt[w][a] + 2 * s1[w][a] * s1[to[i]][b];
s1[w][t] += s1[w][a] * cnt[to[i]][b] + s1[to[i]][b] * cnt[w][a];
s2[w][t] += s2[w][a] * cnt[to[i]][b] + s2[to[i]][b] * cnt[w][a];
cnt[w][t] += cnt[w][a] * cnt[to[i]][b];
}
}
}
}
}
};


## 【BZOJ 3451】Tyvj1953 Normal

### 解题报告

—————————— UPD 2017.4.11 ————————————

## 【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;
}


## 【HDU 5194】DZY Loves Balls

### 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 GCD(int x, int y) {
return y? GCD(y, x % y): x;
}

int main() {
for (int n,m,gcd;~scanf("%d%d",&n,&m);) {
gcd = GCD(n*m, n+m);
printf("%d/%d\n", n*m/gcd, (n+m)/gcd);
}
return 0;
}


## 【Codeforces 712E】Memory and Casinos

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

const int N = 200000+9;

int n,m;
double arr[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;
}

namespace Segment_Tree{
#define SEG Segment_Tree
int ch[N][2],cnt,root,T1,L,R;
double t1[N],t2[N],T2,ans_tmp;

inline void maintain(int w){
t1[w] = t1[ch[w][0]] * t1[ch[w][1]];
t2[w] = t2[ch[w][0]] + t2[ch[w][1]] * t1[ch[w][0]];
}

void Build(int &w, int l, int r) {
w = ++cnt;
if (l == r) {
t1[w] = t2[w] = arr[l];
} else {
int mid = l + r + 1 >> 1;
Build(ch[w][0],l,mid-1);
Build(ch[w][1],mid,r);
maintain(w);
}
}

void modify(int w, int l, int r) {
if (l == r) {
t1[w] = t2[w] = T2;
} else {
int mid = l + r + 1 >> 1;
if (T1 < mid) modify(ch[w][0],l,mid-1);
else modify(ch[w][1],mid,r);
maintain(w);
}
}

inline void modify(int pos, double nv) {
T1 = pos; T2 = nv;
modify(root,1,n);
}

void query(int w, int l, int r) {
if (L <= l && r <= R) {
ans_tmp += t2[w] * T2;
T2 *= t1[w];
} else {
int mid = l + r + 1 >> 1;
if (L < mid) query(ch[w][0],l,mid-1);
if (mid <= R) query(ch[w][1],mid,r);
}
}

inline double query(int l, int r) {
ans_tmp = 0; T2 = 1;
L = l; R = r;
query(root,1,n);
return ans_tmp;
}
};

int main(){
for (int i=1,a,b;i<=n;i++) {
double tmp = (double)a/b;
arr[i] = (1 - tmp) / tmp;
}
SEG::Build(SEG::root,1,n);
for (int i=1,a,b,c,ty;i<=m;i++) {
if (ty == 1) {
double tmp = (double)b/c;
SEG::modify(a,(1-tmp)/tmp);
} else {
double tmp = SEG::query(a,b);
tmp = min(1e20,tmp);
printf("%.10lf\n",1/(1+tmp));
}
}
return 0;
}


## 【Codeforces 696B】Puzzles

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

const int N = 100000+9;

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 Add_Edge(int u, int v){
static int T = 0;
}

void DFS(int w) {
sz[w] = 1;
dep[to[i]] = dep[w] + 1,
DFS(to[i]), sz[w] += sz[to[i]];
}

int main(){
for (int i=1;i<=n;i++) printf("%.1lf ",dep[i]+(n-dep[i]-sz[i])*0.5+1);
return 0;
}


### Code

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

const int MOD = 1000000007;
const int REV = 333333336;
const int N = 100000+9;

LL k,arr[N];

inline int pow(LL w, LL t) {
int ret = 1; while (t) {
if (t & 1) ret = (LL)ret*w % MOD;
w = w*w % MOD; t >>= 1;
} return ret;
}

char c=getchar(); LL 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(){
k = read(); int tag = 1;
for (int i=1;i<=k;i++) tag = ((arr[i] = read()) == 1 && tag);
if (tag) puts("0/1");
else {
LL numerator=REV,denominator=2; tag = -1;
for (int i=1;i<=k;i++) if (arr[i]%2 == 0) tag = 1;
for (int i=1;i<=k;i++) denominator = pow(denominator,arr[i]);
(denominator *= pow(2LL,MOD-2LL)) %= MOD;
(numerator *= denominator + tag) %= MOD;
printf("%d/%d",(int)numerator,(int)denominator);
}
return 0;
}


## 【Codeforces 711E】ZS and The Birthday Paradox

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
#define pow POW
using namespace std;

const LL MOD = 1000003;

char c=getchar(); LL 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 LL pow(LL w, LL t) {
LL ret = 1;
while (t) {
if (t & 1) ret = ret*w % MOD;
w = w*w % MOD; t >>= 1;
}
return ret;
}

inline bool judge(LL n, LL k) {
LL w = 1;
for (int i=1;i<=n;i++) {
w *= 2;
if (w >= k) return false;
} return true;
}

int main(){