双模同余结构

· · 算法·理论

双模数结构、周期引理和同余最短路。

当式子中同时存在 x \bmod p 和 x \bmod q 时,直接拆式子通常难以进行。

在模 q 同余类中讨论。对点 i \in [0,q),连边 i \to (i+p) \bmod q,建出的图一定是若干单环。

将这张图称作双模同余结构。上述讨论将问题转化到模 q 的环上,方便讨论。

弱周期引理,WPL 若 p,q \in \text{per}(S) 且 p+q \le |S|,则 \gcd(p,q) \in \text{per}(S)。

强周期引理,PL 若 p,q \in \text{per}(S) 且 p+q-\gcd(p,q) \le |S|,则 \gcd(p,q) \in \text{per}(S)。

考虑图论建模,对下标 i 连边 i \to i+p 和 i \to i+q,只要证这张图恰有 \gcd(p,q) 个连通块。

这是一种双模同余结构。将 i \to i+q 视作模 q 同余类,每个节点代表相等的字符。连边 i \to (i+p) \bmod q 表示这条边的端点字符相等,只要这张图的连通块数目是 \gcd(p,q)。

这解释了 PL 的下界为何是 p+q-\gcd(p,q)。将 q 个点连成 \gcd(p,q) 个块,边数的下界是 q-\gcd(p,q),即图是森林。

实际上,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[题解]

建立双模同余结构,对 i\in [0,q) 连边 i \to (i+p) \bmod q 形成若干单环。

枚举 i \bmod p=a \in A,则 i 可取 a,a+p,\cdots,a+xp。由 a+xp < k 得 x \le \lfloor \frac{k-a-1}{p} \rfloor+1。问题转化为,在环上从 a \bmod q 开始走 x 步,求路径上有多少个点属于 B。

对每个环预处理环上前缀和即可,询问是对若干次整环和环的一段前缀求和。

:::::

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

:::::