双模同余结构
stripe_python · · 算法·理论
双模数结构、周期引理和同余最短路。
当式子中同时存在
在模
- 环的数目恰为
\gcd(p,q) 。 - 环长恰好是
\frac{q}{\gcd(p,q)}=\frac{\operatorname{lcm}(p,q)}{p} 。
将这张图称作双模同余结构。上述讨论将问题转化到模
弱周期引理,WPL 若
强周期引理,PL 若
考虑图论建模,对下标
这是一种双模同余结构。将
这解释了 PL 的下界为何是
实际上,WPL 对应的图是若干单环,PL 对应的图是若干单链。
P5330 [SNOI2019] 数论
给定
p,q,k 和集合A,B ,求\sum_{i=0}^{k-1} [(i \bmod p) \in A \land (i \bmod q) \in B]
:::::success[题解]
建立双模同余结构,对
枚举
对每个环预处理环上前缀和即可,询问是对若干次整环和环的一段前缀求和。
:::::
:::::info[代码]
#define int long long
const int N = 1e6 + 5;
int p, q, n, m, k, len, ina[N], inb[N];
int cnt, bel[N], pos[N];
vector<int> pre[N];
void dfs(int i, vector<int>& v) {
if (bel[i]) return;
bel[i] = cnt, pos[i] = v.size(), v.emplace_back(i), dfs((i + p) % q, v);
}
void _main() {
cin >> p >> q >> n >> m >> k; len = q / gcd(p, q);
for (int i = 1, x; i <= n; i++) cin >> x, ina[x] = true;
for (int i = 1, x; i <= m; i++) cin >> x, inb[x] = true;
for (int i = 0; i < q; i++) {
if (bel[i]) continue;
vector<int> cur;
cnt++, dfs(i, cur);
pre[cnt].resize(len), pre[cnt][0] = inb[cur[0]];
for (int i = 1; i < len; i++) pre[cnt][i] = pre[cnt][i - 1] + inb[cur[i]];
}
int res = 0;
for (int a = 0; a < p; a++) {
if (!ina[a] || a >= k) continue;
int x = (k - a - 1) / p + 1;
const vector<int>& v = pre[bel[a % q]];
res += x / len * v.back();
if (x % len) {
int l = pos[a % q], r = (l + x % len - 1) % len;
if (l <= r) res += v[r] - (l >= 1 ? v[l - 1] : 0);
else res += v[r] + v.back() - (l >= 1 ? v[l - 1] : 0);
}
} cout << res;
}
:::::