T1 不稳定的道路

题目描述

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

2n105,0m105,1ai,bin,0ci,di1092 \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

思路

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

代码

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

翻转有向图

题目描述

给出了一个 nn 个点和 mm 条边的有向图。顶点编号为 1n1 \sim n。图中没有重边和自环。
对于这 mm 条边,求如果仅反转这一条边,是否会对整个图的强连通分量的数量产生影响?
在这里,反转边 ii 的意思是一条点 aabb 的边,替换为从点 bbaa 的边。

2n1000,1m2×1052 \le n \le 1000,1\le m \leq 2\times10^5

思路

分类讨论。

  1. 原本 uuvv 属于同一个强连通分量,翻转后不属于同一个强连通分量了,此时强连通分量的数量会 +1+1。这种情况要求当前边是从 uuvv 的必经路径,即没有另一条不通过当前边的 uuvv 的路径。同时存在从 vvuu 的路径。

  2. 原本 uuvv 属于同一个强连通分量,翻转后仍然属于同一个强连通分量,此时强连通分量的数量不变,这种情况要求当前边不是从 uuvv 的必经路径,即存在另一条不通过当前边的 uuvv 的路径。同时存在从 vvuu 的路径。

  3. 原本 uuvv 不属于同一个强连通分量,翻转后属于同一个强连通分量,此时强连通分量的数量 1-1,这种情况要求原本不存在 vvuu 的路径(加上翻转的边后存在了),并且存在另一条不通过当前边的 uuvv 的路径。

  4. 原本 uuvv 不属于同一个强连通分量,翻转后仍然不属于同一个强连通分量,此时强连通分量的数量不变,这种情况要求原本不存在 vvuu 的路径(加上翻转的边后存在了),并且当前边是 uuvv 的必经边。

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

  1. 是否存在 vuv \to u 的路径;
  2. 当前边是否为必经边。

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

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

代码

#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×nn \times n 的表格,行和列都以 1n1 \sim n 编号。
在第 行第 列的格子里,他造了许许多多的序列。
这些序列是满足以下要求的所有序列:

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

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

思路

fm(n)f_m(n) 表示满足一下要求的方案数:

  1. 序列长度为给定的正整数 mm
  2. 序列中元素均为 [1,n][1,n] 内的整数;
  3. 序列中元素的最大公约数为 11

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

那么显然有:

d=1nfm(nd)=nmfm(n)=nmd=2nfm(nd)\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(n34)O(n^{\frac{3}{4}}) 的时间内求得 fmf_m 在所有 nx\lfloor \frac{n}{x} \rfloor 的值。

然后开始推柿子:

Ans=d=1fm(nd)i=1nj=1n[gcd(i,j)=d]=d=1fm(nd)i=1ndj=1nd[gcd(i,j)=1]=d=1fm(nd)(2i=1ndφ(i)1)\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(n34)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;
}