1. 求$C_{n}^{k}~mod~10^{9}+7$的值。

$n \leq 200000, k < 2^{31}$

【题解】

暴力求逆元即可。

# include <stdio.h>

using namespace std;

typedef long long ll;
int n, k;
ll ans = 1;
const ll MOD = 1e9+7;

inline ll power(ll a, ll b) {
	ll s=1;
	while(b) {
		if(b&1) s=s*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return s;
}

int main() {
	freopen("video.in", "r", stdin);
	freopen("video.out", "w", stdout);
	
	scanf("%d%d", &n, &k);
	
	if(n<k) {
		puts("0");
		return 0;
	}
	
	for (int i=n-k+1; i<=n; ++i) ans = ans * i % MOD;
	for (int i=1; i<=k; ++i) ans = ans * power(i, MOD-2) % MOD;
	
	printf("%d\n", (int)ans);
	return 0;
}

2. 给出$n$个筐，第$i$个筐里有$R_i - L_i + 1$个球，上面的编号分别为$L_i, L_i+1, ..., R_i$。现在从每个筐里摸出一个球，问最后$n$个球中，编号首位是$1$的占$n$个球中的$k%$的概率。

$n \leq 2000, 0 < k < 100, 0 \leq Li, Ri \leq 10^{18}$

【题解】

先随便算出每个筐符合条件的概率设为$p_i$。

然后Dp，设$f_{i,j}表示前$i$个筐取出了$j$个符合条件的球的概率。

$f_{i,j} = f_{i-1,j-1} \times p_i + f_{i-1, j} \times (1-p_i)$，其中$f_{0,0}=1$。

最后答案就是$i$从$\frac{nk}{100}$上取整到$n$之内的所有$f_{n,i}$值之和。

# include <stdio.h>
# include <math.h>
using namespace std;

typedef unsigned long long ull;
typedef long double ld;
int n, k;
ld p[2010];
ld f[2010][2010];

int wl[20], wln=0, wr[20], wrn=0;

inline void get(int len, ull& begin, ull& end) {
	begin=1; end=0;
	for (int i=1; i<len; ++i) begin=begin*10;
	for (int i=1; i<len; ++i) end=end*10+9;
	end += begin;
}

inline void count(ull l, ull r, int pos) {
	wln=wrn=0;
	ull cnt=0, tl=l, tr=r, lb, le, rb, re;
	while(tl) {wl[++wln]=tl%10; tl/=10;}
	while(tr) {wr[++wrn]=tr%10; tr/=10;}
	for (int i=wln+1; i<=wrn-1; ++i) {
		ull tmp=1;
		for (int j=1; j<i; ++j) tmp=tmp*10;
		cnt+=tmp;
	}
	get(wln, lb, le);
	get(wrn, rb, re);
	if(wln == wrn) {
		if(lb <= l && l <= le && rb <= r && r <= re) {
			cnt += (r-l+1);
		} else if(lb <= l && l <= le) cnt += (le-l+1);	
	} else {
		if(lb <= l && l <= le) {
			cnt += (le-l+1);
		}
		if(rb <= r && r <= re) {
			cnt += (r-rb+1);
		} else {
			ull tmp=1;
			for (int j=1; j<wrn; ++j) tmp=tmp*10;
			cnt += tmp;
		}
	}
	p[pos]=(ld)cnt/(ld)(r-l+1);
}

int main() {
	freopen("chance.in", "r", stdin);
	freopen("chance.out", "w", stdout);
	ull tl, tr;
	scanf("%d%d", &n, &k);
	for (int i=1; i<=n; ++i) {
		scanf("%I64u%I64u", &tl, &tr);
		count(tl, tr, i);
	}
	f[0][0]=1;
	for (int i=1; i<=n; ++i) {
		for (int j=0; j<=i; ++j) {
			f[i][j] = f[i-1][j]*(1-p[i]);
			if(j!=0) f[i][j] = f[i][j] + f[i-1][j-1]*p[i];
		}
	}
	ld avl = ceil((ld)k/100*n);
	ld ans = 0;
	for (int i=avl; i<=n; ++i)
		ans=ans+f[n][i];
	printf("%.10lf\n", (double)ans);
	return 0;		
}

3. 给出一棵$n$个点的树，现在每个叶子节点向根连边，变成一张图。$q$组询问，每次询问$(u, v)$间的最短路径以及在最短路径的情况下，路径上经过的权值最大是多少。图有点权无边权。

$n \leq 100000, q \leq 200000$

【题解】

分类：①直接在树上走；②u到叶子到根到v；③v到叶子到根到u；④u到叶子到根到叶子到v

发现我们要求的只是$f_x$，表示$x$节点到离他最近的叶子节点的距离。

两边dp就求出来了，套个倍增LCA即可。

# include <stdio.h>
# include <vector>
# include <string.h>
# include <iostream>
# include <string>
typedef long long ll;
# define pli pair<ll,int>
# define MP make_pair
using namespace std;

const int N=100020, M=2000010;
int n, q;
int tot=0, head[N], next[M], to[M], w[N];
int fa[N][20], g[N][20], dep[N];
ll h[N][20];
pli f[N];
int sz[N];

inline void add(int u, int v) {
	++tot;
	next[tot]=head[u];
	head[u]=tot;
	to[tot]=v;
}

inline void dfs(int x, int fat) {
	dep[x]=dep[fat]+1;
	fa[x][0] = fat;
	g[x][0] = w[x];
	h[x][0] = w[x];
	for (int i=1; i<=19; ++i) fa[x][i] = fa[fa[x][i-1]][i-1];
	for (int i=1; i<=19; ++i) g[x][i] = max(g[x][i-1], g[fa[x][i-1]][i-1]);
	for (int i=1; i<=19; ++i) h[x][i] = h[x][i-1]+h[fa[x][i-1]][i-1];
	for (int i=head[x];i;i=next[i]) {
		if(to[i] == fat) continue;
		dfs(to[i], x);
	}
}

inline pli lca(int u, int v) {
	int mx = 0; ll dis=0;
	if(dep[u]<dep[v]) swap(u, v);
	for (int i=19; i>=0; --i) 
		if(dep[u]>dep[v] && ((dep[u]-dep[v])&(1<<i)))
			mx=max(mx, g[u][i]), dis = dis + h[u][i], u = fa[u][i];
	if(u==v) return MP(dis+w[u], max(mx, w[u]));
	for (int i=19; i>=0; --i) {
		if(fa[u][i] != fa[v][i]) {
			mx = max(mx, g[u][i]);
			mx = max(mx, g[v][i]);
			dis = dis + h[u][i] + h[v][i];
			u = fa[u][i], v = fa[v][i];
		}
	}
	mx = max(mx, w[u]);
	mx = max(mx, w[v]);
	dis = dis + w[u] + w[v];
	if(fa[u][0] != v && fa[v][0] != u) dis = dis + w[fa[u][0]], mx = max(mx, w[fa[u][0]]);
	return MP(dis, mx);
}

inline void dp(int x, int fa) {
	sz[x] = 0;
	f[x].first = 1000000010000000ll;
	for (int i=head[x]; i; i=next[i]) {
		if(to[i] == fa) continue;
		dp(to[i], x);
		if(f[to[i]].first+w[x] < f[x].first || (f[to[i]].first+w[x] == f[x].first && max(f[to[i]].second, w[x]) > f[x].second))
			f[x] = MP(f[to[i]].first+w[x], max(f[to[i]].second, w[x]));
		++sz[x];
	}
	if(sz[x] == 0) f[x] = MP(w[x], w[x]);
}

inline void dp2(int x, int fa) {
	for (int i=head[x]; i; i=next[i]) {
		if(to[i] == fa) continue;
		if(f[to[i]].first > f[x].first + w[to[i]] || (f[x].first+w[to[i]] == f[to[i]].first && max(f[x].second, w[to[i]]) > f[to[i]].second)) 
			f[to[i]] = MP(f[x].first+w[to[i]], max(f[x].second, w[to[i]]));
		dp2(to[i], x);	
	}
}

inline void out(string s, pli a) {
	cout << s << " = " << a.first << " " << a.second << endl;
}

int main() {
	freopen("plutotree.in", "r", stdin);
	freopen("plutotree.out", "w", stdout);
	scanf("%d%d", &n, &q);
	for (int i=2, t; i<=n; ++i) {
		scanf("%d", &t);
		add(t, i);
		add(i, t);
	}
	for (int i=1; i<=n; ++i) scanf("%d", &w[i]);
	dfs(1, 0);
	dp(1, 0);
	dp2(1, 0);
	//for (int i=1; i<=n; ++i) printf("%d %d\n", f[i].first, f[i].second);
	while(q--) {
		int u, v;
		scanf("%d%d", &u, &v);	
		// ====== 1. LCA ====== //
		pli ans1 = lca(u, v);
		//out("ans1", ans1);
		// ====== 2. down - root - v ====== //
		pli ans2t1 = lca(1, v);
		pli ans2t2 = f[u];
		//out("ans2t1", ans2t1);
		//out("ans2t2", ans2t2);
		pli ans2 = MP(ans2t1.first+ans2t2.first, max(ans2t1.second, ans2t2.second));
		//out("ans2", ans2);
		// ====== 3. down - root - u ====== //
		pli ans3t1 = lca(1, u);
		pli ans3t2 = f[v];
		//out("ans2t1", ans3t1);
		//out("ans2t2", ans3t2);
		pli ans3 = MP(ans3t1.first+ans3t2.first, max(ans3t1.second, ans3t2.second));
		//out("ans3", ans3);
		// ====== 4. down - root - up - v ===== //
		pli ans4t1 = f[v];
		pli ans4t2 = f[u];
		pli ans4 = MP(ans4t1.first+ans4t2.first+w[1], max(max(ans4t1.second, ans4t2.second), w[1]));
		//out("ans4", ans4);
		if(ans2.first < ans1.first || (ans2.first == ans1.first && ans2.second > ans1.second)) ans1 = ans2;
		if(ans3.first < ans1.first || (ans3.first == ans1.first && ans3.second > ans1.second)) ans1 = ans3;
		if(ans4.first < ans1.first || (ans4.first == ans1.first && ans4.second > ans1.second)) ans1 = ans4;
		printf("%I64d %d\n", ans1.first, ans1.second);
	}
	return 0;
}