某金牌训练营Day9

$F_u$ 表示点u被占领的最早时刻, $F_u$ 显然之和子孙有关

于是我们发现至少有 $d_u$ 名士兵到达点u的最早时刻之和其子树信息有关

二分答案

对于一个子孙x,对于u到达的t时刻的贡献为 $max\{0,t-f_x-dis_{u,x}\}$

即会对于他的攻陷贡献这么多士兵!

直接对于每个点暴力dfs其子树就能做到 $O(n^2logW)$

W是值域

$C_{u,v}=f_v+dis(u,v)$

如果我们有这样一个序列 $b_u$ ,存下了所有排好序的 $c_{u,v}$

你会发现有贡献的是一个前缀,是可以二分出来的

然后我们就会发现如果是排列,每次我们只需要维护全局加,然后插入元素两个操作,这个使用平衡树维护,每次只需要打标记,然后插入一个单点,每次在平衡树上二分即可...

这样 $O(nlogn)$ 就能解决一条链了

您不是链?

还只需要维护全局加标记

现在我们还需考虑怎么合并一颗子树

启发式合并!

每次我们把小的全部取出来插入大的即可

用splay实现,每次按照中序遍历插入所有点,势能分析一下复杂度就是 $O(nlogn)$ 的

怎么实现 $O(logn)$ 二分?

考虑在序列上二分到x位置,然后对于x位置对应的数t,以及x+1位置对应的t',因为我们已经知道所有现在和,所以随着t增加对应的数和会上升,他们对应到序列上就相当于能够大于 $d_u$ 的时间在t到t'之间!(或t之前)

所以我们每个位置判断的条件就是看第一个超过的位置在哪里,如果在这之间说明合法,否则不行

方案就是直接连边,所以我们只需要判断无解

直接做要用floyed传递闭包...不太行

但是你会发现我们只和可达性有关,因此我们可以对于一个强联通分量直接缩点,之后图会变成一个DAG

那么我们可以在这上面dp, $f_{u,i}$ 表示点u能否到达点i,然后按照拓扑序dp即可,这个复杂度为 $O(n^2)$

考虑实际上第二维就是一01数组,因此我们可以直接bitset优化,把每一个字节都充分利用,时间复杂度变为 $O(\frac{n^2}{w})$

然后就是经典套路,我们可以把所有可达关键点分块,每1w个做一次即可

时间复杂度就是 $O(\frac{n^2}{w})$ ,但是空间变为 $O(\frac{n*10000}{w})$

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 7;
const int MAXM = 3e5 + 7;
int n, m, flg, t;
struct rec {
	int x, y;
} e[MAXM], a[MAXM];

int home[MAXM], nxt[MAXM], to[MAXM], ccnt, in[MAXM];
inline void ct(int x, int y) {
	ccnt++;
	nxt[ccnt] = home[x];
	to[ccnt] = y;
	home[x] = ccnt;
	in[y]++;
}

int dfn[MAXM], low[MAXM], depp, st[MAXM], tp, bel[MAXM], fl[MAXM];

inline void tarjan(int u) {
	st[++tp] = u;
	fl[u] = 1;
	dfn[u] = low[u] = ++depp;
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		} else if(!fl[v])continue;
		low[u] = min(low[u], dfn[v]);
	}
	if(low[u] == dfn[u]) {
		while(st[tp] != u) {
			int v = st[tp];
			--tp;
			bel[v] = u;
			fl[v] = 0;
		}
		--tp;
		bel[u] = u;
		fl[u] = 0;
	}
	return ;
}
const int B = 10000;
bitset < B + 3 > cv[MAXN]; //标记一些关键点,然后回答即可
//q记录了拓扑序...
int q[MAXM], hd, tl, vis[MAXM];
inline void tpsort() {
	hd = 1, tl = 0;
	for(int i = 1; i <= n; ++i)if(in[i] == 0 && bel[i] == i) {
			q[++tl] = i;
		}
	while(hd <= tl) {
		int u = q[hd];
		++hd;
		for(int i = home[u]; i; i = nxt[i]) {
			int v = to[i];
			--in[v];
			if(in[v] == 0) {
				q[++tl] = v;
			}
		}
	}
	for(int i = tl; i >= 1; i -= B) {
		for(int j = 1; j <= tl; ++j) {
			vis[q[j]] = B;//只有这个不可能有1
			cv[q[j]].reset();//qaq
		}
		for(int j = i; j >= max(i - B + 1, 1); --j) {
			int u = q[j];
			vis[u] = i - j;
			cv[u].set(i - j);//注意,点u的编号是i-j
		}
		for(int j = tl; j >= 1; --j) {
			int u = q[j];
			for(int i = home[u]; i; i = nxt[i]) {
				int v = to[i];
				cv[u] |= cv[v];//解决他们
			}
		}
		for(int k = 1; k <= t; ++k) {
			if(cv[bel[a[k].x]].test(vis[bel[a[k].y]])) {
				flg = 0;
				break;
			}
		}
		if(!flg)break;
	}
	return ;
}

inline void init() {
	for(int i = 1; i <= n; ++i)if(!dfn[i])tarjan(i);
	ccnt = 0;
	memset(home, 0, sizeof(home));
	memset(in, 0, sizeof(in));
	for(int i = 1; i <= m; ++i) {
		if(bel[e[i].x] == bel[e[i].y])
			continue;
		ct(bel[e[i].x], bel[e[i].y]);//可能有重边...
	}

	return ;
}

inline void outans() {
	puts("YES");
	printf("%d\n", m);
	for(int i = 1; i <= m; ++i) {
		printf("%d %d\n", e[i].x, e[i].y);
	}
	return ;
}

int main() {
	freopen("gplt.in", "r", stdin);
	freopen("gplt.out", "w", stdout);
	scanf("%d", &n);
	scanf("%d", &m);
	for(int i = 1; i <= m; ++i) {
		scanf("%d%d", &e[i].x, &e[i].y);
		ct(e[i].x, e[i].y);
	}
	scanf("%d", &t);
	for(int i = 1; i <= t; ++i)
		scanf("%d%d", &a[i].x, &a[i].y);
	init();//建图
	flg = 1;
	for(int i = 1; i <= t; ++i) {
		if(bel[a[i].x] == bel[a[i].y]) {
			flg = 0;
			break;
		}
	}
	tpsort();
	if(flg)
		outans();
	else
		puts("NO");
	return 0;
}

对于偶数

$\forall 1 \leq i \leq n,s_i=s_{2i\mod (n+1)}$

对于奇数

$\forall 1 \leq i < n,s_i=s_{2i\mod (n)}$

现在可以直接建图做了

但是说我们还要再看看对于i和哪些是连边的

$i$ 会和 $2^ki(mod n+1)$ 连边

实际上这样一定会成环

首先2和n+1互质,不用多说

$i$ 的出度为1, $2i\mod n+1$ 的入度为1..

然后我们会发现2有逆元,也就是说2不是1,也就是说每次乘一定会变为一个新的数,而且每个i对应的 $2i$ 都不同,因为如果相同,2又和x+1互质,能推出两个不同的i相同....

每个连通块都是一个环了

定义 $ord(r)$ ,满足 $2^r\equiv 1(\mod p)$ ,因为2和p互质,r必定存在

现在考虑怎么算每个连通块大小,就是 $ord(i)$

会发现 $i$ 只和 $gcd(i,x+1)$ 有关... $d=gcd(i,x+1)$

现在我们要求解 $i*2^r\equiv i (\mod n+1)$ ,最小的r

我们会发现同时可以除掉d,因为 $2^r$ 和 $n+1$ 一定互质,我们有

$\frac{i}{d}2^{r}\equiv \frac{i}{d}(\mod \frac{n+1}{d})$

此时因为互质存在逆元我们就能除掉

$2^{r}\equiv 1(mod \frac{n+1}{d})$

于是最小正整数解就是 $ord(\frac{n+1}{(n+1,i)})$

现在已经知道大小,考虑怎么算对于一个固定的d的环总点数

不难发现这个等价于有多少个数他和x+1的gcd为d就是:

$\sum_{i=1}^x[(i,x+1)==d]$

然后 $\sum_{i=1}^{\frac{x}{d}}[gcd(\frac{i}{d},\frac{x+1}{d})=1]$

$=\phi(\frac{x+1}{d})$

又因为我们ord为环的大小,已经知道环的点数和,直接除就是环数

所以 $G(x)=\sum_{d|(x+1),d!=1}\frac{\phi((x+1)/d)}{ord((x+1)/d)}=\sum_{d|(x+1),d!=1}\frac{\phi(d)}{ord(d))}$

$\leq 1e5$ ?

不难发现这个ord可以暴力求,然后phi可以直接筛

对于 $1到\sqrt R$ ,我们可以发现大于他的这只会有1个,很好算

我们对于太小的p

我们可以直接枚举p的在 $[L,R]$ 范围内的倍数分解对应位置的数,这样的质因数分解是可的,最后还剩下不为1的,说明他们有一个大于根号R的因子,没有关系

然后我们就能知道对应的phi了,利用积性函数即可, $phi(p^k)=(p-1)*p^{k-1}$

考虑怎么计算阶,有结论 $ord(xy)=lcm(ord(x),ord(y))$

证明有 $a=ord(x)$ , $if~2^b\equiv 1(\mod x)$ ,那么 $a|b$

因为如果不满足这个条件,那么我们有 $2^{b-a}\equiv 1(\mod x)$

然后可以辗转相减得到更小的a,这样与ord定义不符

然后怎么求质数幂的阶

可以枚举每个数的约数,然后对于 $ord(p^k)$ ,他一定是 $\phi(p^k)$ 的一个约数,否则我们环甚至是不满的.......

而且还有 $2^{\phi(p^k)}\equiv 1(\mod x+1)$

这个感性理解就是我们因为是约数,所以就有了...

因此我们可以对于 $\phi(p^k)$ 质因数分解,然后 $t=\phi(p^k)$

枚举 $\phi(p^k)$ 每个质因数w,如果 $2^{\frac{t}{w}}\equiv 1(\mod p^k)$ 对应更新t为 $\frac{t}{w}$ ,最后求出的就是 $ord(p^k)$

然后用x的质因数dfs求出x的因数即可,这个因数个数和只有 $O(nlogn)$ ,所以我们就做完啦

其实就是用数论中的欧拉函数把置换变成循环最后利用数论知识化简

李队讲课

n是偶数可以转换为n是奇数的情况

于是2和n互质

然后我们怎么找到阶,直接找到所有约数然后不断试除即可

夏晓光(loveJY)的博客

CF1401