https://vjudge.net/contest/411103

K - Largest Common Submatrix

 

题意：给定两个矩阵，求最大相同子矩阵。

单调栈

先预处理出每个位置最长的竖向相同的长度，再遍历每行，单调栈求这一行最大的矩阵大小。

注意每次新加入单调栈中时不能存当前位置，而应该存最早的大于当前长度的位置，因为这之间虽然在栈里被删掉了但是仍然是能取到的。

细节比较多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;

int n, m;
int a[1010][1010], b[1010][1010];
int len[1010][1010];
int l[N], r[N], u[N], d[N];
typedef pair<int, int>pii;
stack<pii>st;
int ans = 1;
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)scanf("%d", &a[i][j]);
	for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)scanf("%d", &b[i][j]);
	for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) {
		l[b[i][j]] = b[i][j - 1];
		r[b[i][j]] = b[i][j + 1];
		u[b[i][j]] = b[i - 1][j];
		d[b[i][j]] = b[i + 1][j];
	}
	for (int j = 1; j <= m; j++) {
		len[n][j] = 1;
		for (int i = n - 1; i >= 1; i--) {
			if (d[a[i][j]] == a[i + 1][j])len[i][j] = len[i + 1][j] + 1;
			else len[i][j] = 1;
			ans = max(ans, len[i][j]);
		}
	}
	for (int i = 1; i <= n; i++) {
		while (!st.empty())st.pop();
		int p = 1;
		for (int j = 1; j <= m; j++) {
			if (l[a[i][j]] != a[i][j - 1]) {
				while (!st.empty()) {
					ans = max(ans, (j - st.top().first)*st.top().second);
					st.pop();
				}
				p = j;
			}
			int s = j;
			while (!st.empty() && st.top().second >= len[i][j]) {
				ans = max(ans, (j - st.top().first + 1)*len[i][j]);
				ans = max(ans, (j - st.top().first)*st.top().second);
				s = min(s, st.top().first);
				st.pop();
			}
			st.push({ s,len[i][j] });
		}
		while (!st.empty()) {
			ans = max(ans, (m + 1 - st.top().first)*st.top().second);
			st.pop();
		}

	}
	printf("%d\n", ans);
	return 0;
}

 

H - Delivery Route

 

题意：给定一张包含有向边和无向边的图，都有边权，有向边边权可能为负，无向边只为非负，保证若存在 u 到 v 的有向边，则 v 不可能走到 u，求从 s 出发到其它点的最短路。

强连通分量缩点+拓扑排序+Dij最短路

有负环，SPFA会T。

对于每一个只由无向边组成的强连通分量缩点，把他们拓扑排序，按照拓扑序对每个强连通分量求最短路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
int n, x, y, s;
struct E {
	int v, w;
};
vector<E>G[2][N];
vector<int>g[N], scc[N];
typedef pair<int, int>pii;
int d[N];
int sccno[N], tot, du[N];
queue<int>q;
void dfs(int u) {
	if (sccno[u])return;
	sccno[u] = tot;
	scc[tot].push_back(u);
	for (E& e : G[0][u]) {
		dfs(e.v);
	}
}
void bfs(int sc) {
	priority_queue < pii, vector<pii>, greater<pii> >q;
	for (int u : scc[sc]) {
		if (d[u] != INF)q.push({ d[u],u });
	}
	while (!q.empty()) {
		int u = q.top().second, di = q.top().first; q.pop();
		if (di > d[u])continue;
		for (E& e : G[0][u]) {
			int v = e.v, w = e.w;
			if (d[v] > d[u] + w) {
				d[v] = d[u] + w;
				q.push({ d[v],v });
			}
		}
		for (E& e : G[1][u]) {
			int v = e.v, w = e.w;
			if (d[v] > d[u] + w) {
				d[v] = d[u] + w;
			}
		}
	}
}
int main() {
	scanf("%d%d%d%d", &n, &x, &y, &s);
	for (int i = 1; i <= x; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		G[0][u].push_back({ v,w });
		G[0][v].push_back({ u,w });
	}
	for (int i = 0; i < y; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		G[1][u].push_back({ v,w });
	}
	for (int i = 1; i <= n; i++) {
		if (!sccno[i]) {
			tot++;
			dfs(i);
		}
	}
	for (int u = 1; u <= n; u++) {
		for (E& e : G[1][u]) {
			g[sccno[u]].push_back(sccno[e.v]);
			du[sccno[e.v]]++;
		}
	}
	for (int i = 1; i <= tot; i++) {
		if (!du[i])q.push(i);
	}
	memset(d, 0x3f, sizeof(d));
	d[s] = 0;
	while (!q.empty()) {
		int sc = q.front(); q.pop();
		bfs(sc);
		for (int v : g[sc]) {
			du[v]--;
			if (du[v] == 0)q.push(v);
		}
	}
	for (int i = 1; i <= n; i++) {
		if (d[i] == INF)puts("NO PATH");
		else printf("%d\n", d[i]);
	}
	return 0;
}
/*
7 5 3 4
1 2 5
3 4 5
5 6 10
5 7 4
6 7 105
3 5 - 100
4 6 - 100
7 2 - 100

5 2 2 1
1 2 1
3 4 1
4 2 -10
3 5 -10
*/

 

D - Easy Problem

 

题意：对于每一个长度为 nn，且每个元素 1≤ai≤m1\le a_i\le m，且 gcd 为 DD 的数列，求 (a1⋅a2⋯an)k(a_{1}\cdot a_{2} \cdots a_{n})^{k}，再求和。(1≤n≤10100000),(1≤m≤100000),(1≤D≤100000),(1≤k≤109)(1 \leq n \leq 10^{100000}),(1 \leq m \leq 100000),(1 \leq D \leq 100000),(1 \leq k \leq 10^9)。

即求

∑a1=1m∑a2=1m⋯∑an=1m[gcd⁡(a1,a2,⋯ ,an)=1](a1⋅a2⋯an)k\sum_{a_1=1}^m\sum_{a_2=1}^m\cdots \sum_{a_n=1}^m[\gcd(a_1,a_2,\cdots,a_n)=1](a_1\cdot a_2\cdots a_n)^k

莫比乌斯函数+欧拉降幂

∑a1=1m∑a2=1m⋯∑an=1m[gcd⁡(a1,a2,⋯ ,an)=D](a1⋅a2⋯an)k=∑a1=1⌊mD⌋∑a2=1⌊mD⌋⋯∑an=1⌊mD⌋[gcd⁡(a1,a2,⋯ ,an)=1]⋅Dkn(a1⋅a2⋯an)k=∑a1=1⌊mD⌋∑a2=1⌊mD⌋⋯∑an=1⌊mD⌋∑d∣gcd⁡(a1,a2,⋯ ,an)μ(d)⋅Dkn(a1⋅a2⋯an)k=Dkn⋅∑d=1⌊mD⌋μ(d)∑a1=1⌊mDd⌋∑a2=1⌊mDd⌋(a1k⋅a2k⋯ank)⋅dkn=Dkn⋅∑d=1⌊mD⌋μ(d)dkn⋅(∑i=1⌊mDd⌋ik)n\begin{align} & \sum_{a_1=1}^m\sum_{a_2=1}^m\cdots \sum_{a_n=1}^m[\gcd(a_1,a_2,\cdots,a_n)=D](a_1\cdot a_2\cdots a_n)^k\\ &= \sum_{a_1=1}^{\lfloor\frac{m}{D}\rfloor}\sum_{a_2=1}^{\lfloor\frac{m}{D}\rfloor}\cdots\sum_{a_n=1}^{\lfloor\frac{m}{D}\rfloor}[\gcd(a_1,a_2,\cdots,a_n)=1]\cdot D^{kn}(a_1\cdot a_2\cdots a_n)^k\\ &= \sum_{a_1=1}^{\lfloor\frac{m}{D}\rfloor}\sum_{a_2=1}^{\lfloor\frac{m}{D}\rfloor}\cdots\sum_{a_n=1}^{\lfloor\frac{m}{D}\rfloor}\sum_{d|\gcd(a_1,a_2,\cdots ,a_n)}\mu(d)\cdot D^{kn}(a_1\cdot a_2\cdots a_n)^k\\ &= D^{kn}\cdot \sum_{d=1}^{\lfloor\frac{m}{D}\rfloor}\mu(d)\sum_{a_1=1}^{\lfloor\frac{m}{Dd}\rfloor}\sum_{a_2=1}^{\lfloor\frac{m}{Dd}\rfloor}(a_1^k\cdot a_2^k \cdots a_n^k)\cdot d^{kn}\\ &= D^{kn}\cdot \sum_{d=1}^{\lfloor\frac{m}{D}\rfloor}\mu(d)d^{kn}\cdot (\sum_{i=1}^{\lfloor\frac{m}{Dd}\rfloor}i^k)^n\\ \end{align}

预处理出 ∑ik\sum i^k.

由于 nn 很大，所以不能快速幂，需要欧拉降幂。

学到了扩展欧拉定理，把欧拉降幂三个式子合成一个。ab≡ab％ϕ(m)+ϕ(m)(mod　m)a^b\equiv a^{b％\phi(m)+\phi(m)}(mod 　m)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 59964251;
int T;
ll phi;
ll m, D, k, n;
char s[N];
ll sum[N];
ll Pow(ll a, ll b) {
	ll res = 1;
	while (b) {
		if (b & 1)res = res * a%mod;
		b >>= 1;
		a = a * a%mod;
	}
	return res;
}
int mu[N], p[N], tot;
bool flg[N];
void getMu() {
	mu[1] = 1;
	for (int i = 2; i < N; ++i) {
		if (!flg[i]) p[++tot] = i, mu[i] = -1;
		for (int j = 1; j <= tot && i * p[j] < N; ++j) {
			flg[i * p[j]] = 1;
			if (i % p[j] == 0) {
				mu[i * p[j]] = 0;
				break;
			}
			mu[i * p[j]] = -mu[i];
		}
	}
}
int main() {
	getMu();
	ll t = mod;
	phi = t;
	for (ll i = 2; i*i <= t; i++) {
		if (t%i == 0) {
			phi = phi / i * (i - 1);
			while (t%i == 0)t /= i;
		}
	}
	if (t > 1)phi = phi / t * (t - 1);
	scanf("%d", &T);
	while (T--) {
		scanf("%s%lld%lld%lld", s, &m, &D, &k);
		for (int i = 1; i <= m / D; i++)sum[i] = (sum[i - 1] + Pow(i, k)) % mod;
		ll ans = 0;
		n = 0;
		for (int i = 0; s[i]; i++) {
			n = (n * 10 % phi + s[i] - '0') % phi;
		}
		for (int d = 1; d <= m / D; d++) {
			ll tmp = mu[d] * Pow((sum[d] - sum[d - 1] + mod) % mod, n%phi + phi) % mod*Pow(sum[m / D / d], n + phi) % mod + mod;
			ans = (ans + tmp) % mod;
		}
		printf("%lld\n", ans*Pow(D, k*n%phi + phi) % mod);
	}
	return 0;
}