ABC212

AtCoder Beginner Contest 212

E - Safety Journey

题意

给出一个含有 $N(N\leqslant 5000)$ 个顶点的完全图，编号从1到N，从中删去 $M(M\leqslant 5000)$ 条边，要求每次从1号顶点出发，经过 $K(K\leqslant 5000)$ 个顶点后，再次返回到1号顶点，求一共有多少种方案数(结果对 $998244353$ 取模)

思路

最一开始在想通过邻接矩阵的取 $K$ 次幂直接计算答案，但是发现不好优化矩阵乘法

发现这类计数问题可以使用dp解决，记一次路径通过的点分别为 $A_0,A_1,\ldots,A_K(A_0=A_K=1)$

令 $f(i,j)$ 为走 $i$ 步最后到达的城市为 $j$ 的总方案数，也就是 $A_i=j$

则转移方程有：

$$f(i+1,j)=\sum_{k\in S_j}f(i,k)$$

其中，$S_j$ 为顶点 $j$ 所能到达的其他顶点集合

但是这样的转移的复杂度为 $O(N)$，总复杂度为 $O(N^2K)$，没有用到 $M$ 的范围

可以通过求一个补集来用到 $M$

令 $\bar{S_j}$ 为顶点 $j$ 不能到达的顶点集合

于是转移方程又可以写做：

$$f(i+1,j)=\sum_{1\leqslant k\leqslant n}f(i,k)-\sum_{k\in\bar{S_j}}f(i,k)$$

这样每次转移第二维的复杂度为 $O(N+2M)$，则总复杂度为 $O(N^2+2MN)$，就可以过了

初始化：$f(0,i)=\delta_{i,1}=\begin{cases}1\quad i=1\\ 0\quad otherwise\end{cases}$

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m, k;
	cin >> n >> m >> k;
	vii a(n+1);
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		a[u].pb(v);
		a[v].pb(u);
	}
	vii dp(k+1, vi(n+1));
	dp[0][1] = 1;
	for (int i = 0; i < k; i++) {
		int sum = 0;
		for (int j = 1; j <= n; j++) {
			sum = (sum + dp[i][j]) % P;
		}
		for (int j = 1; j <= n; j++) {
			dp[i+1][j] = (sum - dp[i][j] + P) % P; //注意自身不能到达自身
			for (auto k : a[j]) {
				dp[i+1][j] = (dp[i+1][j] - dp[i][k] + P) % P;
			}
		}
	}
	cout << dp[k][1] << '\n';
	return 0;
}

F - Greedy Takahashi

题意

给出N个城市编号从1到N，有M辆巴士，对于每个巴士有四个参数a，b，s，t，分别这辆巴士表示在s+0.5时刻从a城市出发，在t+0.5时刻到达b城市

有一个旅行家，每次都会选择当前时间最近的巴士上车，前往下一个城市，如此往复，直到没有没有巴士可以乘坐，输入保证每个巴士的s值都不相同，就说明他每次的选择都是唯一的

现在有Q次询问，每次询问给出x，y，z，表示在x时刻该旅行家在y城市，求在z时刻时，旅行家所处的位置，如果他正好在某个巴士上，输出巴士对应的城市a和b，否则输出他正处于的城市编号

$N,M,Q\leqslant 10^5$

思路

由于旅行家的这种选择巴士的方法，导致他每次选择具有唯一性，就说明两两巴士之间的关系一定是唯一的

乘坐了A巴士那么如果有下一辆巴士B，那么B一定是唯一的
可以视为A和B之间连接了一条有向边
那么每一个巴士都有且只有一个后继
则这些巴士这就构成了一棵树

题目要求最后停止的时间，可以通过树上倍增完成，需要注意在细节上的判断

时间复杂度 $O(QlogN)$

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
//#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
const int M = 1e5 + 10;
struct Bus {
	int a, b, s, t;
};
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m, Q;
	cin >> n >> m >> Q;
	vector<Bus> bus(m);
	vip star(n+1);
	for (int i = 0; i < m; i++) {
		cin >> bus[i].a >> bus[i].b >> bus[i].s >> bus[i].t;
		star[bus[i].a].pb({bus[i].s, i});
	}
	for (auto &p : star) sort(p.begin(), p.end());
	vii jp(m, vi(20));
	for (int i = 0; i < m; i++) {
		auto it = lower_bound(star[bus[i].b].begin(), star[bus[i].b].end(), mkp(bus[i].t, -1));
		if (it == star[bus[i].b].end()) {
			jp[i][0] = i;
		} else {
			jp[i][0] = it->second;
		}
	}
	for (int j = 1; j < 20; j++) {
		for (int i = 0; i < m; i++) {
			jp[i][j] = jp[jp[i][j-1]][j-1];
		}
	}
	while (Q--) {
		int x, y, z;
		cin >> x >> y >> z;
		auto it = lower_bound(star[y].begin(), star[y].end(), mkp(x, -1));
		if (it == star[y].end() || z <= it->first) {
			cout << y << '\n';
			continue;
		}
		int p = it->second;
		if (z <= bus[p].t) {
			cout << bus[p].a << ' ' << bus[p].b << '\n';
			continue;
		}
		for (int i = 19; i >= 0; i--) {
			if (bus[jp[p][i]].t < z) {
				p = jp[p][i];
			}
		}
		int q = jp[p][0];
		if (z > bus[q].t) {
			cout << bus[q].b << '\n';
		} else if (z <= bus[q].s) {
			cout << bus[q].a << '\n';
		} else {
			cout << bus[q].a << ' ' << bus[q].b << '\n';
		}
	}
	return 0;
}

G - Power Pair

题意

给出一个素数 $p$，求有多少对二元有序对 $(x,y)$ 满足下列条件：

• $0\leqslant x,y \leqslant p-1$
• $\exists n\in \mathbb Z_{\geqslant 1}$ 使得 $x^n\equiv y\pmod p$

答案对 $998244353$ 取模。

思路

当 $x=0$ 时，$y=0$，反之亦然，则一定存在有序对 $(0,0)$，下面考虑 $1\leqslant x, y\leqslant p-1$ 的情况

由于这个题和次幂有关，所以我们考虑取 $p$ 的一个原根 $g$。

由于 $g^1,g^2,\ldots,g^{p-1}$ 遍历模 $p$ 的完全剩余系，则只用考虑 $(g^k)^n$ 在模 $p$ 下的数的个数。

不难发现，这个个数就是它的阶：$\delta_p(g^k)$

又由阶的性质命题5得：

$$\delta_p(g^k)=\frac{\delta_p(g)}{gcd(\delta_p(g), k)}=\frac{\varphi(p)}{gcd(\varphi(p), k)}=\frac{p-1}{gcd(p-1, k)}$$

于是题目变为，求解

$$\sum_{1\leqslant k\leqslant p-1}\frac{p-1}{gcd(p-1,k)}$$

但这样直接求解会是 $O(P)$ 的复杂度会超时，但将 $p-1$ 的因数提出来，然后转换为计数问题就能求解了，也就是：

$$\text{原式}=\sum_{a\mid(p-1)}\frac{p-1}{a} f(a)$$

其中 $\displaystyle f(a)= \sum_{gcd(p-1, k)=a} 1 = \sum_{gcd(\frac{p-1}{a}, \frac{k}{a})=1}1 = \varphi(\frac{p-1}{a})$，也就是和 $p-1$ 的最大公因数为 $a$ 的数的个数。

由于 $a$ 的取值一共只有 $p-1$ 因数的个数那么多，记 $p-1$ 的因数个数为 $d$，用容斥的思想求解 $f(a)$，可以通过从大到小计算 $f(a)$，每次计算的复杂度为 $O(d)$，如：

$$p-1=100, f(10) = 100/10 - f(20) - f(50) - f(100)$$

也就是

$$f(a) = \frac{p-1}{a} - \sum_{a\mid b,\ b\mid (p-1)} f(b)$$

复杂度为 $O(d^2)$

则总复杂度为 $O(\sqrt{P}+d^2)$

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
vi fact;
vp prim;
void dfs(int now, int mul) {
	if (now == (ll)prim.size()) {
		fact.pb(mul);
		return;
	}
	dfs(now+1, mul);
	for (int i = 1; i <= prim[now].second; i++) {
		mul *= prim[now].first;
		dfs(now+1, mul);
	}
}
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int p, ans = 1;
	cin >> p;
	int t = p-1;
	for (int i = 2; i * i <= t; i++) {
		if (t % i == 0) {
			int cnt = 0;
			while (t % i == 0) {
				t /= i;
				cnt++;
			}
			prim.pb({i, cnt});
		}
	}
	if (t != 1) prim.pb({t, 1});
	dfs(0, 1);
	sort(fact.begin(), fact.end());
	int n = fact.size();
	vi num(n);
	for (int i = n-1; i >= 0; i--) {
		num[i] = (p-1) / fact[i];
		for (int j = i+1; j < n; j++) {
			if (fact[j] % fact[i] == 0) {
				num[i] -= num[j];
			}
		}
		ans = (ans + num[i] % P * ((p-1) / fact[i] % P)) % P;
	}
	cout << ans << '\n';
	return 0;
}