백준19514 Intersection is Not Allowed!

작성일 | In

문제 링크

  • http://icpc.me/19514

사용 알고리즘

  • LGV Theorem

시간복잡도

  • $O(N + \log P + K^3)$

풀이

LGV 정리를 이용해 해결할 수 있습니다.
$(1, a_i)$에서 $(N, b_j)$로 가는 경우의 수는 $N+\vert a_i-b_j\vert - 1 \choose N - 1$이므로 $K \times K$ 행렬 $M(i, j) = {N+\vert a_i-b_j\vert - 1 \choose N - 1}$의 determinant를 구하면 됩니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MOD = 1e9+7;

ll Pow(ll a, ll b){
    ll res = 1;
    for(; b; b >>= 1, a = a * a % MOD) if(b & 1) res = res * a % MOD;
    return res;
}
ll Inv(ll v){ return Pow(v, MOD-2); }
ll Add(ll a, ll b){ return (a + b) % MOD; }
ll Sub(ll a, ll b){ return (a - b + MOD) % MOD; }
ll Mul(ll a, ll b){ return a * b % MOD; }
ll Div(ll a, ll b){ return a * Inv(b) % MOD; }
bool IsZero(ll a){ return a == 0; }

template<typename T> // return {rref, rank, det, inv}
tuple<vector<vector<T>>, T, T, vector<vector<T>>> Gauss(vector<vector<T>> a, bool square=true){
    int n = a.size(), m = a[0].size(), rank = 0;
    vector<vector<T>> out(n, vector<T>(m, 0)); T det = T(1);
    for(int i=0; i<n; i++) if(square) out[i][i] = T(1);
    for(int i=0; i<m; i++){
        if(rank == n) break;
        if(IsZero(a[rank][i])){
            T mx = T(0); int idx = -1; // fucking precision error
            for(int j=rank+1; j<n; j++) if(!IsZero(a[j][i])) idx = j;
            if(idx == -1 || IsZero(a[idx][i])){ det = 0; continue; }
            for(int k=0; k<m; k++){
                a[rank][k] = Add(a[rank][k], a[idx][k]);
                if(square) out[rank][k] = Add(out[rank][k], out[idx][k]);
            }
        }
        det = Mul(det, a[rank][i]);
        T coeff = Div(T(1), a[rank][i]);
        for(int j=0; j<m; j++) a[rank][j] = Mul(a[rank][j], coeff);
        for(int j=0; j<m; j++) if(square) out[rank][j] = Mul(out[rank][j], coeff);
        for(int j=0; j<n; j++){
            if(rank == j) continue;
            T t = a[j][i]; // Warning: [j][k], [rank][k]
            for(int k=0; k<m; k++) a[j][k] = Sub(a[j][k], Mul(a[rank][k], t));
            for(int k=0; k<m; k++) if(square) out[j][k] = Sub(out[j][k], Mul(out[rank][k], t));
        }
        rank++;
    }
    return {a, rank, det, out};
}

constexpr int S = 200'000;
ll F[S+1], I[S+1];
ll C(int n, int r){ return r <= n ? F[n] * I[r] % MOD * I[n-r] % MOD : 0LL; }
ll H(int n, int r){ return C(n+r-1, n-1); }

int N, K, A[111], B[111];

void Solve(){
    cin >> N >> K;
    for(int i=0; i<K; i++) cin >> A[i];
    for(int i=0; i<K; i++) cin >> B[i];
    vector<vector<ll>> M(K, vector<ll>(K));
    for(int i=0; i<K; i++) for(int j=0; j<K; j++) M[i][j] = H(N, B[j]-A[i]);
    cout << get<2>(Gauss(M)) << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    F[0] = 1; for(int i=1; i<=S; i++) F[i] = F[i-1] * i % MOD;
    I[S] = Inv(F[S]); for(int i=S-1; i>=0; i--) I[i] = I[i+1] * (i+1) % MOD;
    int TC; cin >> TC;
    for(int tc=1; tc<=TC; tc++) Solve();
}