T1 不稳定的道路

题目描述

有 $n$ 个城市和 $m$ 条道路。城市编号至，道路编号 $1$ 到 $n$ 。道路 $i$ 双向连接城市 $a_i$ 和城市 $b_i$ 。
但是通过每一条道路，所需的时间却是不稳定的，跟出发的时刻有关，如果在时刻 $t$ 通过道路 $i$ ，那么需要的时间
为： $c_i + \lfloor \frac{d_i}{t + 1} \rfloor$ 。其中 $c_i$ 和 $d_i$ 是给出的整数，并且上面这个式子的计算需要向下取整。
你计划从城市 $1$ 去往城市 $n$ ，这个过程中你可以在任何城市进行停留（不必立即出发）。问最早到达城市 $n$ 的时
间。如果无法到达城市 $n$ ，请输出 $-1$ 。

$2 \le n \le 10^5,0 \le m \le 10^5,1 \le a_i, b_i \le n, 0 \le c_i, d_i \le 10^9$

思路

对于时刻 $t$ ，当 $t > \sqrt{d_i} + 1$ 的时候必然不需要等待，当 $t < \sqrt{d_i} - 1$ 时，一定要等待。这是因为此时等待的每一秒带来的贡献一定大于等待的时间，也就是一定是有益的。因此有效的边权，不超过 $4$ 个。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 10;

priority_queue<pair<ll, ll> > Heap;
vector<tuple<ll, ll, ll> > G[MAXN];
ll N, M;
bitset<MAXN> Book;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N >> M;
	for (int i = 1; i <= M; i++) {
		static ll a, b, c, d;
		cin >> a >> b >> c >> d;
		G[a].emplace_back(b, c, d);
		G[b].emplace_back(a, c, d);
	}
	Heap.push({0, 1});
	while (Heap.size()) {
		static ll dis, u;
		tie(dis, u) = Heap.top();
		Heap.pop();
		if (u == N) {
			cout << -dis << endl;
			return 0;
		}
		if (Book[u]) {
			continue;
		}
		Book[u] = true;
		dis *= -1ll;
		for (auto W : G[u]) {
			ll Min = LLONG_MAX;
			for (ll i = max(dis, (ll)sqrt(get<2>(W)) - 2); i <= max(dis, (ll)sqrt(get<2>(W)) + 1); i++) {
				Min = min(Min, i - dis + get<2>(W) / (i + 1));
			}
			Heap.push({-dis - get<1>(W) - Min, get<0>(W)});
		}
	}
	cout << -1 << endl;
	return 0;
}

翻转有向图

题目描述

给出了一个 $n$ 个点和 $m$ 条边的有向图。顶点编号为 $1 \sim n$ 。图中没有重边和自环。
对于这 $m$ 条边，求如果仅反转这一条边，是否会对整个图的强连通分量的数量产生影响？
在这里，反转边 $i$ 的意思是一条点 $a$ 向 $b$ 的边，替换为从点 $b$ 向 $a$ 的边。

$2 \le n \le 1000,1\le m \leq 2\times10^5$

思路

分类讨论。

原本 $u$ 和 $v$ 属于同一个强连通分量，翻转后不属于同一个强连通分量了，此时强连通分量的数量会 $+1$ 。这种情况要求当前边是从 $u$ 到 $v$ 的必经路径，即没有另一条不通过当前边的 $u$ 到 $v$ 的路径。同时存在从 $v$ 到 $u$ 的路径。
原本 $u$ 和 $v$ 属于同一个强连通分量，翻转后仍然属于同一个强连通分量，此时强连通分量的数量不变，这种情况要求当前边不是从 $u$ 到 $v$ 的必经路径，即存在另一条不通过当前边的 $u$ 到 $v$ 的路径。同时存在从 $v$ 到 $u$ 的路径。
原本 $u$ 和 $v$ 不属于同一个强连通分量，翻转后属于同一个强连通分量，此时强连通分量的数量 $-1$ ，这种情况要求原本不存在 $v$ 到 $u$ 的路径（加上翻转的边后存在了），并且存在另一条不通过当前边的 $u$ 到 $v$ 的路径。
原本 $u$ 和 $v$ 不属于同一个强连通分量，翻转后仍然不属于同一个强连通分量，此时强连通分量的数量不变，这种情况要求原本不存在 $v$ 到 $u$ 的路径（加上翻转的边后存在了），并且当前边是 $u$ 到 $v$ 的必经边。

然后我们就发现只需要检验两个条件：

是否存在 $v \to u$ 的路径；
当前边是否为必经边。

第一个条件直接 $\Theta(nm)$ 的搜索就可以了。

第二个条件常规做法为支配树，但是这里有一个人类智慧做法：首先我们以任意一种顺序从 $i$ 的每一个出去的节点出发进行搜索，并且标记每个节点是从那个节点开始搜到的。然后将顺序倒过来再做一遍。如果两次答案相同，则为必经边，因为在第一次遍历后的边无法到达目标节点，也就是唯一的；反之则不为唯一的。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e3 + 10, MAXM = 2e5 + 10;

vector<int> G[MAXN];
int N, M, U[MAXM], V[MAXM], A[MAXN][MAXN], B[MAXN][MAXN];

void DFS(int x, int col, int *a) {
	if (a[x]) return;
	a[x] = col;
	for (int y : G[x]) DFS(y, col, a);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= M; i++) {
		cin >> U[i] >> V[i];
		G[U[i]].push_back(V[i]);
	}
	for (int i = 1; i <= N; i++) {
		A[i][i] = B[i][i] = i;
		for (int j : G[i]) DFS(j, j, A[i]);
		reverse(G[i].begin(), G[i].end());
		for (int j : G[i]) DFS(j, j, B[i]);
	}
	for (int i = 1; i <= M; i++) {
		if ((A[U[i]][V[i]] != B[U[i]][V[i]]) ^ (A[V[i]][U[i]] > 0)) {
			cout << "diff" << endl;
		} else {
			cout << "same" << endl;
		}
	}
	return 0;
}

在表格里造序列

题目描述

他有一张 $n \times n$ 的表格，行和列都以 $1 \sim n$ 编号。
在第行第列的格子里，他造了许许多多的序列。
这些序列是满足以下要求的所有序列：

序列长度为给定的正整数 $m$ ；
序列中元素均为 $[1,n]$ 内的整数；
序列中元素的最大公约数和 $i,j$ 的最大公约数相等。
他突然发现这些序列有好多好多，所以他想具体数一数。
他希望你能帮他数出所有格子里的序列个数之和。
以及，他知道这很困难，所以希望你能将答案对取模。

$1 \le n \le 10^9, 1 \le m \le 10^{18}$

思路

设 $f_m(n)$ 表示满足一下要求的方案数：

序列长度为给定的正整数 $m$ ；
序列中元素均为 $[1,n]$ 内的整数；
序列中元素的最大公约数为 $1$ 。

那么最大公约数为 $d$ 的方案则为 $f_m(\lfloor \frac{n}{d} \rfloor)$ 。

那么显然有：

\sum_{d=1}^n f_m(\lfloor \frac{n}{d} \rfloor) = n^m\\ \Rightarrow f_m(n) = n^m - \sum_{d=2}^n f_m(\lfloor \frac{n}{d} \rfloor)

然后我们就可以在 $O(n^{\frac{3}{4}})$ 的时间内求得 $f_m$ 在所有 $\lfloor \frac{n}{x} \rfloor$ 的值。

然后开始推柿子：

\begin{aligned} Ans &= \sum_{d=1}f_m(\lfloor \frac{n}{d} \rfloor) \sum_{i=1}^n \sum_{j=1}^n [\gcd(i,j) = d]\\ &= \sum_{d=1}f_m(\lfloor \frac{n}{d} \rfloor) \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{n}{d} \rfloor} [\gcd(i,j) = 1]\\ &= \sum_{d=1}f_m(\lfloor \frac{n}{d} \rfloor) \Big(2\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \varphi(i) - 1\Big) \end{aligned}

然后结合杜教筛法即可做到 $O(n^{\frac{3}{4}})$ 。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e6;
const ll MOD = 998244353;

ll Mp_Phi[MAXN], Mp_F[MAXN], le[MAXN], ge[MAXN], ToT;
ll Phi[MAXN + 10], Cnt, Prime[MAXN + 10];
bool Vis[MAXN + 10];

ll Quick_Power(ll a, ll b) {
	ll res = 1;
	while (b) {
		if (b & 1ll) res = res * a % MOD;
		a = a * a % MOD; 
		b >>= 1ll;
	}
	return res;
}

ll N, M, Ans;

ll &Id(ll x) {
    return x <= sqrt(N) ? le[x] : ge[N / x];
}

ll Get_Phi_Sum(ll x) {
	if (x <= MAXN) return Phi[x];
	if (Mp_Phi[Id(x)]) return Mp_Phi[Id(x)];
	ll res = 1ll * x * (x + 1) / 2ll % MOD;
	for (ll l = 2ll, r; l <= x; l = r + 1) {
		r = x / (x / l);
		res = (res - (r - l + 1ll) * Get_Phi_Sum(x / l) % MOD + MOD) % MOD;
	}
	return Mp_Phi[Id(x)] = res;
}

ll Get_F_Sum(ll x) {
	if (Mp_F[Id(x)]) return Mp_F[Id(x)];
	ll res = Quick_Power(x, M);
	for (ll l = 2ll, r; l <= x; l = r + 1) {
		r = x / (x / l);
		res = (res - (r - l + 1ll) * Get_F_Sum(x / l) % MOD + MOD) % MOD;
	}
	return Mp_F[Id(x)] = res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	Phi[1] = 1;
	for (ll i = 2; i <= MAXN; i++) {
		if (!Vis[i]) {
			Prime[++Cnt] = i;
			Phi[i] = i - 1;
		}
		for (ll j = 1; j <= Cnt && i * Prime[j] <= MAXN; j++) {
			Vis[i * Prime[j]] = 1;
			if (!(i % Prime[j])) {
				Phi[i * Prime[j]] = Phi[i] * Prime[j];
				break;
			} else {
				Phi[i * Prime[j]] = Phi[i] * (Prime[j] - 1);
			}
		}
	}
	for (int i = 1; i <= MAXN; i++) {
		Phi[i] = (Phi[i] + Phi[i - 1]) % MOD;
	}
	cin >> N >> M;
	for (ll l = 1, r; l <= N; l = r + 1) {
		r = N / (N / l);
		Id(N / l) = ++ToT;
	}
	for (ll l = 1, r; l <= N; l = r + 1) {
		r = N / (N / l);
		Ans = (Ans + (r - l + 1ll) * (2ll * Get_Phi_Sum(N / l) - 1ll + MOD) % MOD * Get_F_Sum(N / l)) % MOD;
	}
	cout << Ans << endl;
	return 0;
}