CS Academy Divisible Matching

发表于 | 分类于

Description

给定一个\(n\)个点的带边权的二分图，求它的边权和为\(k\)的倍数的完美匹配的数量。

\(1\leq k, n\leq 100\)。

Solution

先来说一下用行列式判定二分图完美匹配是否存在的方法……

先构造矩阵\(A\)满足\(A_{i, j} = x_{i,j}\)（当边\((i, j)\)存在时满足，其他情况为\(0\)，注意这里的\(x\)是两两不同的变量），若\(\det(A) = 0\)则没有完美匹配，反之则有完美匹配。出于方便，我们可以把\(x_{i, j}\)直接搞成随机数。

如果说我们要求是\(k\)的倍数的话，那么我们每个非零的\(A_{i, j}\)还要再乘上一个\(y^{w(i, j)}\)，最后得到的生成函数的指数为\(k\)的倍数的项的系数和就是答案。很显然这个东西可以用单位根反演完成……

不过这里注意没有模数的话我们要自己找一个满足为\(kx + 1\)形式的大质数当模数，考虑到质数分布的那一套玄学理论这个暴力找也是可以的。需要单位根的话当然要求原根力，，，

Code

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <random>
using ll = long long;
ll ha;
inline ll pow_mod(ll a, ll b) {
  ll ans = 1, res = a;
  while(b) {
    if(1LL & b) ans = ans * res % ha;
    res = res * res % ha; b >>= 1;
  }
  return ans;
}
inline ll inv(ll x) {
  return pow_mod(x, ha - 2LL);
}

inline bool is_prime(int x) {
  int bd = (int)floor(sqrt(x));
  for(int i = 2; i <= bd; i ++) {
    if(x % i == 0) return false;
  }
  return true;
}
inline void desc(int x, std::vector<int> &V) {
  int bd = (int)floor(sqrt(x));
  for(int i = 2; i <= bd; i ++) {
    if(x % i == 0) {
      V.push_back(i);
      while(x % i == 0) x /= i;
    }
  }
  if(x > 1) V.push_back(x);
}
inline int find_g() {
  std::vector<int> V; desc(ha - 1, V);
  for(int i = 2; i < ha; i ++) {
    bool ok = true;
    for(int up : V) {
      if(pow_mod(i, (ha - 1LL) / up) == 1LL) {
        ok = false; break;
      }
    }
    if(ok) return i;
  }
}

const int maxn = 105;
ll D[maxn][maxn]; int n;
inline ll det() {
  ll flag = 1;
  for(int i = 1; i <= n; i ++) {
    int r = -1;
    for(int j = i; j <= n; j ++)  {
      if(D[j][i]) {
        r = j; break;
      }
    }
    if(r == -1) return 0;
    if(r != i) {
      flag = ha - flag;
      for(int j = 1; j <= n; j ++) {
        std::swap(D[i][j], D[r][j]);
      }
    }
    ll inv_th = inv(D[i][i]);
    for(int j = i + 1; j <= n; j ++) {
      if(D[j][i]) {
        ll th = inv_th * D[j][i] % ha;
        for(int k = i; k <= n; k ++) {
          D[j][k] = (D[j][k] - th * D[i][k] % ha + ha) % ha;
        }
      }
    }
  }
  ll ans = flag;
  for(int i = 1; i <= n; i ++) {
    ans = ans * D[i][i] % ha;
  }
  return ans;
}

int G[maxn][maxn], A[maxn][maxn];
int main() {
  int k; scanf("%d%d", &n, &k);
  for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= n; j ++) {
      scanf("%d", &G[i][j]);
    }
  }
  ha = (1000000000 / k) * k + 1;
  while(!is_prime(ha)) ha -= k;
  int g = find_g();
#ifdef LOCAL
  printf("ha : %lld\ng : %d\n", ha, g);
#endif
  std::mt19937 gen(114514);
  std::uniform_int_distribution<int> dist(1, (int)ha - 1);
  for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= n; j ++) {
      A[i][j] = dist(gen);
    }
  }
  
  ll ans = 0, xi = 1LL, xi_n = pow_mod(g, (ha - 1LL) / (ll)k);
  for(int i = 0; i < k; i ++) {
    memset(D, 0, sizeof(D));
    for(int u = 1; u <= n; u ++) {
      for(int v = 1; v <= n; v ++) {
        if(G[u][v] == -1) {
          D[u][v] = 0;
        } else {
          D[u][v] = (ll)A[u][v] * pow_mod(xi, G[u][v]) % ha;
        }
      }
    }
    ans = (ans + det()) % ha;
    xi = xi * xi_n % ha;
  }
  ans = ans * inv(k) % ha;
  if(ans == 0LL) puts("No");
  else puts("Yes");
  return 0;
}