CSP-S 模拟赛 36

T1

由于 \(a_i\le 10^5\)，那么考虑枚举这个 \(\gcd\)，考虑求 \(f(i)\) 表示答案，那么 \(\operatorname{ans}=\sum i\times f(i)\)。然而式子中有 \(\gcd\)，于是考虑求 \(g(i)\) 表示 \(i\mid\gcd\) 的方案数，然后 \(f(i)=g(i)-\sum_{j>i,i\mid j}f(j)\)。对于 \(g(i)\)，求出每一行 \(x\) 的倍数即可。

时间复杂度 \(O(n\log n)\)。

代码：

#include <bits/stdc++.h>
#define N 22
#define M 100005
#define int long long
#define mod 1000000007
using namespace std;
int n, m, mx;
int a[N][M];
int bs[N][M];
int cnt[N][M];
int dp[N];
int ans;
signed main() {
	freopen("b.in", "r", stdin);
	freopen("b.out", "w", stdout);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			scanf("%lld", &a[i][j]);
			bs[i][a[i][j]]++;
			mx = max(mx, a[i][j]);
		}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= mx; j++)
			for (int k = 1; k * j <= mx; k++)
				cnt[i][j] += bs[i][k * j];
	for (int i = 1; i <= mx; i++) {
		dp[i] = 1;
		for (int j = 1; j <= n; j++)
			dp[i] = dp[i] * (cnt[j][i] + 1) % mod;
		dp[i] = (dp[i] - 1 + mod) % mod;
	}
	for (int i = mx; i >= 1; i--) {
		for (int j = 2; i * j <= mx; j++)
			dp[i] = (dp[i] - dp[i * j] + mod) % mod;
		ans = (ans + dp[i] * i % mod) % mod;
	}
	cout << ans << "\n";
	return 0;
}

T2

强连通分量问题考虑先对原图缩点，考虑一个被缩点后的不合法的点集一定是一个 DAG。那么对于一个不合法的子图 \(S\)，一定有一个强连通的子图 \(T\)，满足 \(S,T\) 之间的边都是 \(S\rightarrow T\)。其实 \(T\) 集合就是缩点后拓扑序最小的点对应的点集。

那么反向地考虑，对于一个强连通分量 \(S\)，其中每个点的出边的交集是 \(T\)，那么对于 \(T\) 的子集 \(R\)，\(S|R\) 便是不合法的子集。这样一来每个子图都会被遍历一次，时间复杂度 \(O(2^n)\)。

代码：

你被骗了，这里没有代码，不要问我为什么。

T3

抽象题，请稍后再拨。

T4

考虑将边的维护转为点的维护。想到这个基本上这题就完了。显然每次染色相当于对每个点打上一个新的时间戳，时间戳相等的两端就是白色边，否则黑色边。然后就是套路树链剖分。

代码：

你又被骗了，这里没有代码，不要问我为什么。