【BZOJ 4318】OSU!

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4318
神犇题解:https://oi.men.ci/bzoj-4318/

解题报告

设$p_i$为第$i$个操作成功的概率
设$E_{(i,x^3)}$为以第$i$个位置为结尾,$($极长$1$的长度$x)^3$的期望
$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)$

然后就可以直接维护,然后再根据期望的线性加入答案就可以辣!
时间复杂度:$O(n)$

另外,似乎直接算贡献也可以?
可以参考:http://blog.csdn.net/PoPoQQQ/article/details/49512533

Code

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

inline int read() {
	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() {
	int n=read(); 
	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

相关链接

题目传送门:http://codeforces.com/contest/749/problem/E
官方题解:http://codeforces.com/blog/entry/49186

解题报告

考虑从期望的定义下手
就是要求所有区间的逆序对的和
于是我们枚举右端点,然后算贡献
用$BIT$来维护,时间复杂度:$O(n \log n)$

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

inline int read() {
	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() {
	n = read();
	for (int i = 1; i <= n; i++) {
		p[i] = read();
	}
	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)

相关链接

题目传送门:http://codeforces.com/contest/802/problem/L
官方题解:http://dj3500.webfactional.com/helvetic-coding-contest-2017-editorial.pdf

解题报告

这题告诉我们,这类题可以高斯消元做
裸做是$O(n^3)$的,非常不科学
这题我们发掘性质,如果从叶子开始一层一层往上消,高斯消元那一块可以做到$O(n)$
然后再算上逆元的话,总的时间复杂度:$O(n \log n)$

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

inline int read() {
	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;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

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
	n = read();
	for (int i = 1; i < n; ++i) {
		int u = read(), v = read();
		AddEdge(u + 1, v + 1, read());
	}
	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

相关链接

题目传送门:https://community.topcoder.com/stat?c=problem_statement&pm=14568&rd=16881

题目大意

给定一棵$n(n \le 50)$个结点的树,每个点上有一个点权$a_i(a_i \le 10^9)$
让你从中随意选出一个连通子图,询问这个连通子图中的每一个点的权值组成的序列的方差的期望是多少
小数输出,最终误差不得大于$\frac{1}{10^9}$

解题报告

将方差的式子化一化,发现我们大概要维护$E(\sum{a_i^2})$和$E((\sum{a_i})^2)$
第一个可以直接维护
第二个那一坨,我们还是使用期望的线性将其拆开,分别维护即可
最后再做一个树$DP$,总的复杂度大概在$O(n^3)$

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 {
	int n,E,head[N],nxt[M],to[M];
	__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) {
    		E = 1; ans = tot = 0; memset(head,0,sizeof(head));
    		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) {
			to[++E] = v; nxt[E] = head[u]; head[u] = E;
			to[++E] = u; nxt[E] = head[v]; head[v] = E;
		}
		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];
			for (int i=head[w];i;i=nxt[i]) {
				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

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3451
神犇题解:http://wyfcyx.is-programmer.com/posts/74735.html

解题报告

考虑一个点$u$,如果点分到点$v$的时候会产生贡献
那么点分$v$的时候,$v \to u$这个路径上还没有其他点被点分
换一句话来讲,点$v$应该是$v \to u$这条路径上第一个被点分的点
因为每一个点被选的概率一样,所以贡献的概率是$\frac{1}{dis_{u \to v} + 1}$
于是最后答案就是$\sum\limits_{u,v \in [1,n]}{\frac{1}{dis_{u \to v}+1}}$

然后这个东西我们可以使用点分治加上FFT来解决
具体来讲就是在点分的时候统计$dis_{u \to v}=x$的方案数,然后计入答案
时间复杂度:$O(n \log^2 n)$

—————————— UPD 2017.4.11 ————————————
找到这题的序列版了:http://www.lydsy.com/JudgeOnline/problem.php?id=2769
在具体的做法方面,用分个块,然后块内暴力,块间FFT即可

【BZOJ 3925】[ZJOI2015] 地震后的幻想乡

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3925
神犇题解Ⅰ:http://blog.csdn.net/skywalkert/article/details/47792065
神犇题解Ⅱ:http://www.cnblogs.com/yousiki/p/6437155.html

解题报告

题目上说:

对于$n$个$[0,1]$之间的随机变量$x_1,x_2,\cdots ,x_n$,第$k$小的那个的期望值是$\frac{k}{n+1}$

即加入$k$条边后恰好有生成树的情况的最大边的期望权值为$\frac{k}{n+1}$
设$g_k$为加入$k$条边后恰好使所有点连通的方案数
于是原题的答案为$\frac{1}{m+1}\sum\limits_{i=1}^{m}{\frac{i \cdot g_i}{m \choose i}}$

设$f_k$为加入$k$条边后原图不连通的方案数
我们可以交换一下求和顺序可使答案变为:$\frac{1}{m+1}\sum\limits_{i=0}^{m}{\frac{f_i}{m \choose i}}$
于是问题变为求$f_k$与$g_k$

我们首先可以发现,$f_k$加$g_k$一定等于所有的方案
那么设点集$S$的诱导子图中的边数为$cnt_{S}$,仅对于点集$S$有效的$f_k,g_k$为$f_{S,k},g_{S,k}$
则有:$f_{S,k}+g_{S,k}={cnt_S \choose k}$,于是只需要求出$g_{S,k},f_{S,k}$中的任意一个

类比带标号的连通图计数,我们可以列出递推式:$f_{S,i+j} = \sum\limits_{T \subset S}{g_{T,i} {cnt_{S-T} \choose j}}$
又$g_{S,k}={cnt_S \choose k} – f_{S,k}$,所以这个递推式可以直接递推
于是这题就做完啦!时间复杂度:$O(m 4^n)$
又因为上述$T \subset S$所以我们直接枚举子集,复杂度优化到$O(m 3^n)$

【BZOJ 3811】玛里苟斯

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3811
神犇题解Ⅰ:https://blog.sengxian.com/solutions/bzoj-3811
神犇题解Ⅱ:http://yyy.is-programmer.com/posts/200623.html

解题报告

这题这么神,我们来分情况讨论:

1. $k = 1$

这就是一般的期望题。因为期望的线性,所以我们在二进制位下每一位分开考虑:

如果这一位上每一个数都是$0$,那么贡献肯定为$0$
如果有一个数为不为$0$那么我们有贡献的概率为$\frac{1}{2}$

证明的话,可以设$f_{1,0/1}$为考虑到第i个数,异或起来为0/1的概率
写出$DP$式子可以很轻松地发现这俩总是对半分,Q.E.D

于是我们直接把所有数$or$起来,然后除二输出即可
时间复杂度:$O(n)$

2. $k = 2$

这不是一般的期望题了,不是线性的,不能直接加 /(ㄒoㄒ)/~~
但我们发现某一个异或和为$(b_mb_{m-1} \cdots b_0)_{bin}$的话
其中第$i$位与第$j$位的贡献为$b_i \cdot b_j \cdot 2^{i+j}$

因为$b_i$与$b_j$是线性的,所以我们就可以枚举$i,j$然后直接加起来了!
根据$k = 1$时得到的结论,不难发现:

如果这两位独立则贡献的概率为$\frac{1}{4}$
如果这两位不独立,那么贡献的概率为$\frac{1}{2}$
如果这两位中有至少一位从没出现过,那么概率为$0$

于是我们暴力枚举$i,j$直接算贡献就可以了
时间复杂度:$O(62n + 62^2)$

3. $k \ge 3$

我们先来看一个结论:若$E(x^k) < 2^{63}$,初始集合中的每个数小于$2^{22}$
证明的话,sengxian教我的:

不妨用反证法,考虑答案为:$\sum\limits_{s \in \{1,2,\cdots,n\}}{\frac{v^3}{2^n}}$
假如有一个数的二进制下第$22$位出现了$1$,有$2^{n-1}$个集合异或起来后这一位为$1$
所以这一位的贡献就已经为$2^{63}$了,又因为答案小于$2^{63}$,矛盾,故不可能,Q.E.D

所以我们可以求出这些数的线性基,然后暴力枚举线性基的子集
根据$k = 1$时的人生经验,我们又可以得到每一种情况出现的概率相等
于是我们暴力枚举,然后暴力算贡献就可以了
时间复杂度:$O(21n + 2^{21})$

【HDU 4624】Endless Spin

相关链接

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=4624
神犇题解Ⅰ:http://www.cnblogs.com/chanme/p/4869377.html
神犇题解Ⅱ:http://blog.csdn.net/beginendzrq/article/details/51331954

解题报告

我们设$f_i$为染色$i$次后还有球没有被染色的概率
那么我们的答案$ans$为: $\sum\limits_{i = 0}^\infty {{f_i}} $

现在考虑如何求$f_i$,我们先来$O(2^n)$暴力容斥
具体来讲,我们枚举染色$i$次后还剩下哪些球为白色
设还有$k$个球为白色,这$k$个球位置分别为$v_1 \sim v_k$
那么单次染色的区间不能包含这$k$个位置,设合法的方案数为$A$
那么单次染色符合条件的概率$P=\frac{A}{\frac{n(n-1)}{2}}$
那么$i$次都符合要求的概率就是$P^i$
于是对于$f_i$来讲,贡献为$P^i \cdot (-1)^{k-1}$
这种情况对于答案$ans$的贡献为$(-1)^{k-1}\sum\limits_{i=0}^{\infty}{P^i}=\frac{(-1)^{k-1}}{1-P}$

现在考虑优化容斥的过程
我们发现每一种具体的方案对于答案的贡献只与剩余球的数量的奇偶性和$A$有关
于是我们可以搞一个状态为$O(n^4)$,转移为$O(1)$的DP来优化容斥

Code

这份代码在我本地跑出来是对的,但交上去就wa
于是只能打了一份表交上去:http://paste.ubuntu.com/24448347/

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

inline int read() {
	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() {
	for (int T=read();T;T--) {
		ans = ww = 0; pp = 1;
		memset(f,0,sizeof(f));
		f[pp][0][0][0] = 1;
		n = read();
		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;
}

相关拓展

当然这题还可以改成:如果染到$k$个球都为黑色了就停止,询问停止时的期望步数
例题可以参考:凯旋三兵

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

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3566
神犇题解:https://blog.sengxian.com/solutions/bzoj-3566

解题报告

首先根据期望的线性,我们只需要求出每个元件有电的概率,之后相加就是答案
那么怎么求每个元件有电的概率呢?我们可以无脑点分
显然在$O(n)$的时间复杂度内搞一发树形$DP$就可以了

Code

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

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

int n,head[N],nxt[M],to[M]; 
double up[N],down[N],cost[M],q[N],vout;

inline int read() {
	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;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

void DFS1(int w, int f) {
	down[w] = 1 - q[w];
	for (int i=head[w];i;i=nxt[i]) {
		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);
	for (int i=head[w];i;i=nxt[i]) {
		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() {
	n = read();
	for (int i=1,u,v;i<n;i++) {
		u = read(); v = read();
		AddEdge(u, v, read());
	}
	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] 亚瑟王

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4008
神犇题解:https://blog.sengxian.com/solutions/bzoj-4008

解题报告

根据期望地线性,我们可以单独计算每一个技能的期望然后相加
于是问题转化为求每个技能在这$r$轮中被发动的概率

但我们发现如果直接模拟题目中的过程,我们似乎需要记录哪些点已经被使用过
这个问题似乎只能使用状压DP来解决?但复杂度是不允许这么干的
于是我们需要一点Trick:

我们将这$r$轮整体转移,记录$f_{i,j}$表示到第$i$个技能,还有$j$轮没有触发任何技能的概率
那么这个状态的时候第$i$个技能被触发的概率就是$1-(1-p_i)^j$

于是这个问题就做完啦!时间复杂度:$O(Tnr)$
至于为什么是对的?
因为每一轮的游戏过程没有区别,所以我们可以将将其一视同仁

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

inline int read() {
	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() {
	for (int T=read();T;T--) { 
		memset(f,0,sizeof(f)); memset(ans,0,sizeof(ans));
		n = read(); r = read();
		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;
}

【日常小测】随机游走

题目大意

给定一棵$n(n \le 10^5)$个点的无根树,再给定$m(m \le 10^5)$个询问
每次询问给定起点和终点,从起点开始XJB走到终点的期望步数是多少?
定义XJB走为:每次完全随机选择一条出边走出去,可以走回头路

解题报告

如果定义$f_{u,v}$为当前在$u$点,最终走到$v$点的期望步数
那肯定搞一个高斯消元就可以了,但这题数据太大搞不了 QwQ

但我们仔细观察一下,这里的XJB走非常妙啊!目标点、来源点完全不影响决策
于是我们定义$f_u$为这个点走到父亲的期望步数,$g_u$为这个点的父亲走到它的期望步数
那我们就可以推出以下式子:
$$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}}$$
于是我们DFS两遍,然后记个前缀和什么的
询问的时候求出lca然后加加减减就可以辣!
时间复杂度:$O(n \log n)$

Code

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

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

int n,m,head[N],nxt[M],to[M];
int in[N],dep[N],fa[N][20];
LL f[N],g[N],PreF[N],PreG[N];

inline int read() {
	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]++;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

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;
	for (int i=head[w];i;i=nxt[i]) {
		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];
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != anc) {
			g[to[i]] = f[w] - f[to[i]] + g[w];
			DFS2(to[i], w);
		}
	}	
}

int main() {
	n = read();
	for (int i=1;i<n;i++) AddEdge(read(),read());
	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];
		}
	}
	m = read();
	for (int i=1,u,v,lca;i<=m;i++) {
		u = read(); v = read(); lca = LCA(u, v);
		printf("%lld\n",PreF[u]-PreF[lca]+PreG[v]-PreG[lca]);
	}
	return 0;
}

【HDU 5194】DZY Loves Balls

相关链接

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5194
中文题面:http://blog.csdn.net/u014086857/article/details/44724335

解题报告

这题主要就是用到一个“期望的可加性”吧!
什么是可加性呢?

期望的和,等于和的期望

这里不需要期望之间相互独立
证明的话,你可以参见这里:http://blog.csdn.net/grooowing/article/details/45000205

于是这题我们分开考虑每一个位置出现01的概率就好了
于是推一推式子发现答案至于n,m相关,于是写一个gcd就好了

Code

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

inline int read() {
	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

题目传送门:http://codeforces.com/problemset/problem/712/E
官方题解:http://codeforces.com/blog/entry/47050

这个题目想一想,还是挺好玩的
推导过程比较复杂,参见这里吧:http://codeforces.com/blog/entry/47050?#comment-314259
话说这次的官方题解真是辣鸡,还不如评论区容易懂…..

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

const int N = 200000+9;

int n,m;
double arr[N];

inline int read(){
	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(){
	n = read(); m = read();
	for (int i=1,a,b;i<=n;i++) {
		a = read(); b = read();
		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++) {
		ty = read(); a = read(); b = read();
		if (ty == 1) {
			c = read();
			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

题目传送门:http://codeforces.com/contest/696/problem/B
官方题解:http://codeforces.com/blog/entry/46031
中文题面:http://blog.csdn.net/oulaline/article/details/51941548
中文题解:http://blog.csdn.net/TRiddle/article/details/51919455#t12

这个题目好神! 赶紧Mark!
B2%_CMRK155VXE]OXMHHFT4

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

const int N = 100000+9;

int head[N],nxt[N],to[N],n,sz[N],dep[N]; 

inline int read(){
	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;
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
}

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

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

【Codeforces 696C】PLEASE

相关链接

题目传送门:http://codeforces.com/contest/696/problem/C
官方题解:http://codeforces.com/blog/entry/46031
中文题面:http://www.cnblogs.com/DarkTong/p/5674920.html

解题报告

用全概率公式可以推得\(p(i) = – \frac{{1 – p[i – 1]}}{2}\)
然后推一推通项公式可以得到\(p(i) = \frac{{{{( – 1)}^i} + {2^{i – 1}}}}{{3 \cdot {2^{i – 1}}}}\)
然后我们惊奇的发现\({{{( – 1)}^i} + {2^{i – 1}}}\)总可以被3整除
而\({{{( – 1)}^i} + {2^{i – 1}}}\)又是一个奇数,与2的整次幂肯定不能约分
于是搞一搞快速幂什么的就可以了

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

inline LL read(){
	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

题目传送门:http://codeforces.com/problemset/problem/711/E
官方题解:http://codeforces.com/blog/entry/46830
中文题面及题解:https://blog.sengxian.com/solutions/cf-711e

这个题重点不在推概率,而在Legendre’s formula
其实难点就是要求在取MOD之前就约分,这个就很麻烦了,只有用上面那个定理

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

inline LL read(){
	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(){
	LL n = read(), k = read(), tn = pow(2,n);
	if (judge(n,k)) cout<<1<<' '<<1;
	else {
		LL t1, t2, cnt = (k-1) - __builtin_popcountll(k-1), gcd = pow(pow(2,cnt),MOD-2);
		if (k >= MOD) t1 = 0; else {t1 = 1; for (int i=1;i<k;i++) t1 = t1 * (tn - i) % MOD;}
		t2 = pow(pow(2,n),k-1); t2 = t2 * gcd % MOD; t1 = t1 * gcd % MOD; t1 = ((t2 - t1)% MOD + MOD) % MOD;
		cout<<t1<<' '<<t2;
	} 
	return 0;
}

ps:如果不知道上面的那个定理,貌似自己推也是可以推出来的?