概率 – edward

传送门
比赛的时候就很慢很慢地搞出前三题……然后rating加了5，囧
记一下自己犯圡的地方好了。
258A
不说了。
258B
一开始看错题了，但是数位dp的部分还是写得很快的。后来发现看错题以后，感觉后面那部分很难算，用dp写了很久(组合计数也太不熟练了)，总算pass了。
值得记录的一点是即使是分类相同的项里面取，也应该看成有顺序的，最后再乘6!这样的算法比较科学。
实际上最后那一部分10^7的dfs就可以了。对数据范围不够敏感……作为一个ACMer，能暴力就暴力是基本原则。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
template  void checkmin(T &t,T x){if (x < t) t = x;}
template  void checkmax(T &t,T x){if (x > t) t = x;}
template  void _checkmin(T &t, T x){if (t == -1) t = x; if (x < t) t = x;}
template  void _checkmax(T &t, T x){if (t == -1) t = x; if (x > t) t = x;}
typedef pair  PII;
typedef pair  PDD;
typedef long long lld;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
#define DEBUG(a) cout << #a" = " << (a) << endl;
#define DEBUGARR(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }
const int N = 12;
const int Mod = 1000000007;
int n;
int f[N][N][2];
char s[N];

int A6(int x) {
	if (x < 6) return 0;
	long long ret = 1;
	for (int i = 0; i < 6; i++) {
		ret = ret * (x - i);
		ret %= Mod;
	}
	return ret;
}

int Pow(long long a, int b) {
	long long ret = 1;
	while (b) {
		if (b & 1) {
			ret = ret * a;
			ret %= Mod;
		}
		a *= a;
		a %= Mod;
		b >>= 1;
	}
	return ret;
}

int C(int m, int n) {
	if (m < n) return 0;
	long long ret = 1;
	for (int i = 0; i < n; i++) {
		ret = ret * (m - i);
		ret %= Mod;
		ret = ret * Pow(i + 1, Mod - 2);
		ret %= Mod;
	}
	return ret;
}

int main() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	memset(f, 0, sizeof(f));
	f[0][0][1] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int o = 0; o < 2; o++) {
				for (int k = 0; k <= (o ? s[i + 1] - '0' : 9); k++) {
					int &t = f[i + 1][j + (k == 4 || k == 7)][o && (k == s[i + 1] - '0')];
					t += f[i][j][o];
				}
			}
		}
	}
	f[n][0][0] += Mod - 1;
	f[n][0][0] %= Mod;
	int sum = 0;
	int ans = 0;
	int g[25][25][7];
	memset(g, 0, sizeof(g));
	g[0][0][0] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= n; j++) {
			for (int k = 0; k <= 6; k++) {
				g[i + 1][j][k] += g[i][j][k];
				g[i + 1][j][k] %= Mod;
				for (int o = 1; k + o <= 6 && o * i + j <= n && o <= f[n][i][0] + f[n][i][1]; o++) {
					g[i + 1][j + o * i][k + o] += 1LL * g[i][j][k] * C(f[n][i][0] + f[n][i][1], o) % Mod;
					g[i + 1][j + o * i][k + o] %= Mod;
				}
			}
		}
	}
	for (int i = 0; i <= n; i++) {
		ans += 1LL * sum * (f[n][i][0] + f[n][i][1]) % Mod;
		ans %= Mod;
		sum += g[n][i][6] * 720LL % Mod;
//		printf("%d %d\n", i, g[n][i][6]);
		sum %= Mod;
	}
	cout << ans << endl;
}

258C
直接枚举约数然后每个容斥统计。一开始觉得复杂度有点悬，好像是$$O(n\sqrt{n} \log n)$$的，但是突然就想起来[1,n]之间的约数个数应当是$$O(n\log n)$$级别的(参见筛法)，所以整个算法应该是$$O(n\sqrt{n} + n \log^2 n)$$的

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
template  void checkmin(T &t,T x){if (x < t) t = x;}
template  void checkmax(T &t,T x){if (x > t) t = x;}
template  void _checkmin(T &t, T x){if (t == -1) t = x; if (x < t) t = x;}
template  void _checkmax(T &t, T x){if (t == -1) t = x; if (x > t) t = x;}
typedef pair  PII;
typedef pair  PDD;
typedef long long lld;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
#define DEBUG(a) cout << #a" = " << (a) << endl;
#define DEBUGARR(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }

const int N = 105555;
const int Mod = 1000000007;
int n;
int a[N];
int sum[N];
int num[N];

int Pow(long long a, int b) {
	long long ret = 1;
	while (b) {
		if (b & 1) ret = ret * a % Mod;
		a = a * a % Mod;
		b >>= 1;
	}
	return ret;
}

int main(){
	scanf("%d", &n);
	set  Set;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		sum[a[i]]++;
	}
	for (int i = 100000; i >= 0; i--) {
		sum[i] = sum[i + 1] + sum[i];
	}
	long long ans = 0;
	for (int i = 1; i <= 100000; i++) {
		if (sum[i]) {
			vector  vec;
			for (int j = 1; j * j <= i; j++) {
				if (i % j == 0) {
					vec.push_back(j);
					if (j * j != i) vec.push_back(i / j);
				}
			}
			num[i] = vec.size() + 1;
			sort(vec.begin(), vec.end());
			long long ret = 1;
			for (int j = (int)(vec.size()) - 2; j >= 0; j--) {
				int now = sum[vec[j]];
				now -= sum[vec[j + 1]];
				ret = ret * Pow(j + 1, now) % Mod;
			}
			long long tmp = Pow(vec.size(), sum[vec[vec.size() - 1]]) - Pow((int)vec.size() - 1, sum[vec[vec.size() - 1]]);
			tmp += Mod;
			tmp %= Mod;
//			cout << i << " " << ret * tmp << endl;
			ans += 1LL * ret * tmp % Mod;
			ans %= Mod;
		}
	}
	cout << ans << endl;
	return 0;
}

258D
这种算数目的数学期望题……
其实就利用概率论与数理统计之前学到的那个将$$E(x)$$分解为若干个$$E(x_i)$$之和，然后分别算期望，叠加起来就好了。
这些随机变量$$x_i$$之间有关无关都是没有关系的。
至于为什么能这么搞，那是因为E(x)本来计算公式就是线性的……

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
template  void checkmin(T &t,T x){if (x < t) t = x;}
template  void checkmax(T &t,T x){if (x > t) t = x;}
template  void _checkmin(T &t, T x){if (t == -1) t = x; if (x < t) t = x;}
template  void _checkmax(T &t, T x){if (t == -1) t = x; if (x > t) t = x;}
typedef pair  PII;
typedef pair  PDD;
typedef long long lld;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
#define DEBUG(a) cout << #a" = " << (a) << endl;
#define DEBUGARR(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }
const int N = 1005;
int n, m;
int a[N];
double p[N][N];

int main(){
#ifdef cwj
	freopen("in", "r", stdin);
#endif
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			p[i][j] = a[i] > a[j];	
		}
	}
	for (int i = 0; i < m; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		for (int j = 1; j <= n; j++) {
			if (j != x && j != y) {
				p[j][x] = p[j][y] = (p[j][x] + p[j][y]) / 2;
				p[x][j] = p[y][j] = (p[x][j] + p[y][j]) / 2;
			}
		}
		p[x][y] = p[y][x] = 0.5;
	}
	double ans = 0;
	for (int i = 1; i < n; i++) {
		for (int j = i + 1; j <= n; j++) {
			ans += p[i][j];
		}
	}
	printf("%.12lf\n", ans);
}

258E
对这种不要求在线算法的情况，设计一个合理的计算顺序是至关重要，离线算法相对于在线算法的一个很大的优势就在于计算顺序可以按自己调。
这里也不例外。
首先将子树转化为dfs序中连续一段已经是很old的技巧了，然后按dfs序列从左往右扫，每个询问就只进栈两次再出栈两次。
这样只要用线段树统计出目前被覆盖的点的数目就可以了。这个统计的方法类似于用线段树求矩形并的面积。
具体方法就是记录当前区间的最小值以及这个最小值的数目就可以轻松统计出来了。

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N = 100005;
int n, m, ot;
int st[N], ed[N];
int order[N];
vector  E[N];

void dfs(int x, int fa) {
	order[++ot] = x;
	st[x] = ot;
	for (vector ::iterator it = E[x].begin(); it != E[x].end(); it++) {
		if (*it != fa) {
			dfs(*it, x);
		}
	}
	ed[x] = ot;
}

	struct Node {
		int l, r, minv, num, d;
		Node *lc, *rc;
		Node(){}
		Node(int l, int r):l(l), r(r) { num = r - l + 1; minv = d = 0; lc = rc = NULL; }
		bool fit(int _l, int _r) { return _l <= l && r <= _r; }
		void pushdown() {
			if (d) {
				minv += d;
				if (lc) {
					lc->d += d;
					rc->d += d;
				}
				d = 0;
			}
		}

		void update() {
			if (lc) {
				minv = min(lc->minv + lc->d, rc->minv + rc->d);
				num = 0;
				if (lc->minv + lc->d == minv) num += lc->num;
				if (rc->minv + rc->d == minv) num += rc->num;
			}
		}
	}tr[N << 2], *root = &tr[1];

	void build(int p, int l, int r) {
		tr[p] = Node(l, r);
		int mid = (l + r) / 2;
		if (l != r) {
			tr[p].lc = &tr[p * 2];
			tr[p].rc = &tr[p * 2 + 1];
			build(p * 2, l, mid);
			build(p * 2 + 1, mid + 1, r);
		}
	}

	void add(Node *p, int l, int r, int x) {
		p->pushdown();
		if (p->fit(l, r)) {
			p->d += x;
		} else {
			int mid = (p->l + p->r) / 2;
			if (l <= mid) add(p->lc, l, r, x);
			if (r >  mid) add(p->rc, l, r, x);
			p->update();
		}
	}

int a[N], b[N];
int ans[N];
vector  in[N], out[N];

int main() {
	scanf("%d%d", &n, &m);
	for (int x, y, i = 1; i < n; i++) {
		scanf("%d%d", &x, &y);
		E[x].push_back(y);
		E[y].push_back(x);
	}
	dfs(1, 0);
	build(1, 1, n);
	for (int i = 0; i < m; i++) {
		scanf("%d%d", &a[i], &b[i]);
		in[st[a[i]]].push_back(i);
		in[st[b[i]]].push_back(i);
		out[ed[a[i]]].push_back(i);
		out[ed[b[i]]].push_back(i);
	}
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		vector ::iterator it;
		for (it = in[i].begin(); it != in[i].end(); it++) {
			add(root, st[a[*it]], ed[a[*it]], 1);
			add(root, st[b[*it]], ed[b[*it]], 1);
			cnt++;
		}
		ans[order[i]] = root->minv + root->d ? n - 1 : n - root->num - !!cnt ;
		for (it = out[i].begin(); it != out[i].end(); it++) {
			add(root, st[a[*it]], ed[a[*it]], -1);
			add(root, st[b[*it]], ed[b[*it]], -1);
			cnt--;
		}
	}
	for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
}

标签存档：概率

Codeforces Round #157