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


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


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


## 【NOI六连测】[D3T1] 炉石

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

const int MAXN = 100;
const int T = 100000;

double win,lose,arr[MAXN][4],tmp[MAXN][4],ans;
int n;

int main(){
freopen("hearthstone.in","r",stdin);
freopen("hearthstone.out","w",stdout);
scanf("%d%lf",&n,&win);
lose = 1 - win;
arr[96-n][0] = 1;
for (int k=1;k<=T;k++){
for (int i=0;i<=10;i++){
tmp[i][0] += arr[i][0]*lose;
tmp[i][0] += arr[i][1]*lose;
tmp[i][0] += arr[i][2]*lose;
tmp[i][0] += arr[i][3]*lose;
tmp[i+1][1] += arr[i][0]*win;
tmp[i+1][2] += arr[i][1]*win;
tmp[i+2][3] += arr[i][2]*win;
tmp[i+2][3] += arr[i][3]*win;
}
for (int i=11;i<=70;i++){
tmp[i-1][0] += arr[i][0]*lose;
tmp[i-1][0] += arr[i][1]*lose;
tmp[i-1][0] += arr[i][2]*lose;
tmp[i-1][0] += arr[i][3]*lose;
tmp[i+1][1] += arr[i][0]*win;
tmp[i+1][2] += arr[i][1]*win;
tmp[i+2][3] += arr[i][2]*win;
tmp[i+2][3] += arr[i][3]*win;
}
for (int i=71;i<=95;i++){
tmp[i-1][0] += arr[i][0]*lose;
tmp[i-1][0] += arr[i][1]*lose;
tmp[i-1][0] += arr[i][2]*lose;
tmp[i-1][0] += arr[i][3]*lose;
tmp[i+1][1] += arr[i][0]*win;
tmp[i+1][2] += arr[i][1]*win;
tmp[i+1][3] += arr[i][2]*win;
tmp[i+1][3] += arr[i][3]*win;
}
ans += (tmp[96][0]+tmp[96][1]+tmp[96][2]+tmp[96][3])*k;
memcpy(arr,tmp,sizeof(tmp));
memset(tmp,0,sizeof(tmp));
}
printf("%.2lf\n",ans);
return 0;
}