Cydiater

「CSAcademy #67 G」Divisible Matching

给定一张大小为$n$的二分图,每条边都有一个边权,询问其中是否存在一个完美匹配,满足各边权的和为$k$的倍数。

前几天刚学习了一下基于线代的一般图匹配就出了道相似的题呢~

首先我们把这个图转化成矩阵,对于 $A_{i, j}$来说,如果存在从$i$到$j$的边,那么$A_{i,j} = x_{i,j}$,注意这里的$x$是一个变量。然后根据矩阵行列式的定义,我们发现只要满足这个矩阵的行列式不为$0$,那么显然存在一个完美匹配。为了方便计算,我们直接把每个变量看看作一个随机数处理即可。

然后我们发现,对于一个完美匹配来说,他对于行列式的贡献是$\pm \prod x_{i,j}$。我们考虑这样一种构造,我们任取一个大质数$p$满足$k|(p - 1)$,然后取$p$的原根的$\frac{p - 1} {k}$次方,不妨设为$x$。

然后我们重新构造矩阵,令$A_{r,i,j} = A_{i, j}\times x^{a_{i,j} \times r}$。

得到 $ans = \sum\limits_{r = 0}^{k - 1} \det (A_r)$

容易发现,如果一个完美匹配的边权和在模$k$的意义下不为$0$,那么其对$ans$的贡献和为$0$。

即对于一个完美匹配的边权和$ss$来说,假设所有边变量以及符号的乘值是$v$,那么其对$ans$的贡献是

$$v\times (1 + x^{ss} + x^{2ss} + …+x^{(k - 1)\times ss})$$

根据等差数列的求和公式,很容易证明。

于是这题就做完啦,时间复杂度$O(n^3k)$

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define db            double
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pr            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define bin(i)        (1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}

const int MAXN = 105;

int mod;

inline int add(int a, int b){a += b; return a >= mod ? a - mod : a;}
inline int pop(int a, int b){a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b){return 1LL * a * b % mod;}

int qpow(int a, int b){
    int c = 1;
    while (b) {
        if (b & 1) cmul(c, a);
        cmul(a, a); b >>= 1;
    }
    return c;
}

inline int lrand(int l, int r){return l + 1LL * rand() * rand() % (r - l + 1);}

int N, K, a[MAXN][MAXN], e[MAXN][MAXN], xx[MAXN][MAXN];

inline bool isprime(int p){
    int n = sqrt(p);
    up (i, 2, n) if (p % i == 0) return 0;
    return 1;
}

inline bool vaild(int g){
    int n = sqrt(mod - 1), p = mod - 1;
    up (i, 2, n) if (p % i == 0) {
        if (qpow(g, (mod - 1) / i) == 1) return 0;
        while (p % i == 0) p /= i;
    }
    if (p > 1 && qpow(g, (mod - 1) / p) == 1) return 0;
    return 1;
}

int det(){
    int sum = 1;
    up (i, 1, N) {
        up (j, i, N) if (a[j][i]) {
            up (k, i, N) swap(a[i][k], a[j][k]);
            if (j > i) sum = pop(0, sum);
            break;
        } 
        if (!a[i][i]) return 0;
        int inv = qpow(a[i][i], mod - 2);
        up (j, i + 1, N) {
            int d = mul(a[j][i], inv);
            up (k, i, N) cpop(a[j][k], mul(a[i][k], d));
        }
    }
    up (i, 1, N) cmul(sum, a[i][i]);
    return sum;
}

int main(){
    srand(19260817);
    scanf("%d%d", &N, &K);
    up (i, 1, N) up (j, 1, N) scanf("%d", &e[i][j]);
    mod = (int)(1e9 / K) * K  + 1; 
    while (!isprime(mod)) mod -= K;
    int g = 2;
    while (!vaild(g)) g++;
    g = qpow(g, (mod - 1) / K);
    int T = 1;
    while (T--) {
        up (i, 1, N) up (j, 1, N) xx[i][j] = e[i][j] == -1 ? 0 : lrand(1, mod - 1); 
        int ans = 0;
        up (d, 0, K - 1) {
            up (i, 1, N) up (j, 1, N) {
                if (e[i][j] == -1) a[i][j] = 0;
                else a[i][j] = mul(xx[i][j], qpow(g, d * e[i][j]));
            }
            cadd(ans, det());
        }
        if (ans != 0) return 0 * puts("Yes");
    }
    puts("No");
    return 0;
}