2022 ICPC 济南站 E - Identical Parity // exgcd

题目来源：2022 International Collegiate Programming Contest, Jinan Site E

题目链接：https://codeforces.com/gym/104076/problem/E

题意

有 \(T\) 组案例，对于每个案例：

给定整数 \(n\)、\(k\)，问是否存在一种 \([1,n]\) 的排列，使得对于该排列所有长度为 \(k\) 的子区间，它们区间和的奇偶性相同。

数据范围：\(1 \le T \le 10^5\)，\(1 \le k \le n \le 10^9\).

思路：exgcd

可以视作有一个长度为 \(k\) 的移动窗口，每次只会进入连续的 \(k\) 个数，那么其往后移动一格时，就会弹出一个数，同时进入一个数，若要使得奇偶性保持不变，那么这两个数的奇偶性是需要一致的，于是满足条件的排列，应该满足：\(p_i\ mod\ 2 \equiv p_{i+k}\ mod\ 2\)，其中 \(1 \le i \le n - k\)。

于是整个排列可以按照 \(i\ mod\ k\) 的值，划分成 \(k\) 块，我们需要为每个块分配奇偶性，其中，包含数字数量为 \(\lfloor \frac{\large n}{\large 2} \rfloor\) （记为 \(a\)）的块的数量为 \(k - n\ mod\ k\)（记为 \(p\)），包含数字数量为 \(\lfloor \frac{\large n}{\large 2} \rfloor + 1\) （记为 \(b\)）的块的数量为 \(n\ mod\ k\)（记为 \(q\)）。

我们需要解决的问题实际上就是，找到一组整数解 \((x,y)\)，使得 \(xa + yb = \lfloor \frac{\large n}{\large 2} \rfloor\)，\(x \in [0,p]\)，\(y \in [0,q]\) 同时成立。这个等式和取值限制的意义是，能找到一组合法的分配方案，使得取偶数的块的数字总数量等于 \([1,n]\) 范围内的偶数数量。

对于这个等式，可以用 exgcd 求得一组解 \((x_0,y_0)\)，由于 \(gcd(a,b)=1\)，那么通解就是 \((x_0 + m·b,y_0-m·a)\)，根据两个取值范围的限制，可以二分或者公式，分别求出 \(m\) 的取值范围 \([l_x,r_y]\)，\([l_y,r_y]\)，判断 \(max(l_x,l_y) \le min(r_x,r_y)\) 是否成立即可。

时间复杂度：\(O(T·logn)\).

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

int exgcd(int a, int b, int& x, int& y)
{
    if(!b) {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, x, y);
    int tmp = x;
    x = y, y = tmp - a / b * y;
    return d;
}

void solve()
{
    int n, k;
    cin >> n >> k;

    int a = n / k, p = k - n % k;
    int b = n / k + 1, q = n % k;

    int x, y;
    int d = exgcd(a, b, x, y);

    if(n / 2 % d) {
        cout << "No" << '\n';
        return;
    }

    x = x / d * (n / 2), y = y / d * (n / 2);

    int l = -1e9, r = 1e9;
    int l1 = r;
    while(l <= r) {
        int mid = l + r >> 1;
        if(x + mid * (b / d) >= 0) r = mid - 1, l1 = mid;
        else l = mid + 1;
    }

    l = -1e9, r = 1e9;
    int r1 = l;
    while(l <= r) {
        int mid = l + r >> 1;
        if(x + mid * (b / d) <= p) l = mid + 1, r1 = mid;
        else r = mid - 1;
    }

    l = -1e9, r = 1e9;
    int l2 = r;
    while(l <= r) {
        int mid = l + r >> 1;
        if(y - mid * (a / d) <= q) r = mid - 1, l2 = mid;
        else l = mid + 1;
    }

    l = -1e9, r = 1e9;
    int r2 = l;
    while(l <= r) {
        int mid = l + r >> 1;
        if(y - mid * (a / d) >= 0) l = mid + 1, r2 = mid;
        else r = mid - 1;
    }

    cout << (max(l1, l2) <= min(r1, r2) ? "Yes" : "No") << '\n';
}

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int test;
    cin >> test;
    while(test--) solve();

    return 0;
}