Wuyanru's blog
0%

[QOJ10514] 疲配

发表于 分类于 ，

感觉很有难度的线性代数题。

题目链接。

题意

给定一张左右侧各 个点的二分图，图中没有重边且每一条边都有一个 中的颜色。

对于一个颜色的子集 ，我们称它是好的，当且仅当存在一组完美匹配，使得该匹配只用了 中的颜色，并且每种个颜色都出现过。

现在可以进行至多一次修改操作，可以将一条边的颜色改为其相邻的颜色， 和 也算相邻的颜色。

对于每一种颜色，输出是否存在一种修改方案，使得修改之后它是好的。

，。

题解

首先考虑如何用代数方法判断一个二分图是否存在完美匹配。

考虑一个 的矩阵 ，若左侧第 个点与右侧第 个点之间没有边则 ，否则 ，其中 为一个变量。

考虑 的值，容易发现 当且仅当这个二分图有完美匹配。

那么我们随机取一个大质数 ，并给所有 赋一个随机值。

若这样计算出 ，我们认为这个二分图有完美匹配，容易发现这样做错误率不超过 。

再来考虑，如果不能进行修改操作，怎么判断一个颜色子集是否是好的。

我们更改一下上述矩阵，如果有边的话，我们令 。

其中 表示左侧第 个点到右侧第 个点的边的颜色； 为一个关于边的颜色的变量。

特别的，我们定义 这一位的乘法为或卷积，也就是说有 。

考虑此时行列式计算的结果，每一个项上某一个 的指数都一定是 或 。

也就是说，我们算出来的直接就是，能否恰好使用某个子集的颜色，构成一组完美匹配。

再来考虑代码实现，首先给 随机带入一些值。

考虑不给 带入随机值，直接维护每一项的具体系数。

现在我们要求行列式的值，考虑 这一项相乘，也就是两个 数组做或卷积的过程。

其实就是两个数组先 FMT，再按位相乘，然后再 IFMT。

如果我们要计算多个数组相乘，显然不用每一次都 FMT 再 IFMT，只需要所有数组都先 FMT，然后每一位都乘起来，然后乘完再 IFMT 回去。

这里我们直接先做好 FMT，然后直接拆成 个行列式分别求值，然后再 IFMT 就好了。

这样我们的复杂度是 ，可以算出不进行修改操作的答案。

现在需要考虑，我们还可以使用一次修改操作。

再次更改那个矩阵的定义，我们令 。

我们新引入一个变量 ，表示当前使用了几次修改操作。

那么显然 这一位需要普通乘法而不是或卷积，然后只需要保留 和 两项。

还是对 那一位做 FMT，拆位之后我们需要计算一个类似 的东西的 和 项。

如果只是求出 和 项的话，我们有一个比较简单的方法能直接做出来。

比较牛的事情在于，我们有一个做法，可以在 的时间复杂度内，求出这个行列式的所有项！

首先我们将 消成单位矩阵。

对于第 行，我们找一个 的位置，然后将其换到第 列，然后将这一列上下的 全消掉。

特殊的，如果我们找不到 非空的位置，我们就给这一行整体 ，这样常数项就变成了一次项。

由于我们乘完之后，这个矩阵仍然至多只有一次项，所以如果我们执行了 次操作，矩阵的行列式就一定是 。

值得注意的的事情是，由于我们给这一行乘了 ，这一行前面的部分需要重新消一下。

在做完之后， 矩阵就只在对角线上有值了。

接下来考虑将 消成上海森堡矩阵，但我们对行列做操作的时候， 的值也会改变，需要注意这一点。

对于第 列，我们先看下面的位置是否有常数项，没有的话这一列直接就做完了，直接看下一列。

如果有的话，设其为第 列，我们现在让 上有常数项，如果 那么就已经好了。

否则，我们给第 行加上第 行，此时常数项满足了，但是 上出现了一次项。

那么我们给第 列整体减去第 列，这样操作之后仍然只有对角线上的位置有一次项。

现在我们考虑消去第 列在第 行以下所有的常数项。

此时如果 这个位置有常数项，我们用第 行的常数项给他消掉。

此时可能会导致 这个位置有一次项，我们再用第 列把第 列的常数项消掉。

这样常数项就被消成了一个上海森堡矩阵。

这样我们就可以考虑 dp 求行列式的值了。

考虑行列式的原定义，就是选一个列的排列，然后将所有位置乘起来。

那么这个东西显然是好 dp 的。

整道题时间复杂度为 。

代码

成功拿下最劣解（

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
template<typename A,const int N>
using aya=array<A,N>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
// mt19937_64 _rand(time(0)^clock());
mt19937_64 _rand(0);
const int mod=1004535809;
ll A[55][55],B[55][55];
ll dp[55][55];
int c[55][55];
ll V[55][55];
ll ans0[1024];
ll ans1[1024];
int n,m,k;
inline ll qow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
inline void Add(ll &a,ll b){ (a+=b)%=mod;}
inline void add1(int i,int j,ll y)//row : i+=j*y
{
    y=(y%mod+mod)%mod;
    for(int p=1;p<=n;p++)
    {
        Add(A[i][p],A[j][p]*y);
        Add(B[i][p],B[j][p]*y);
    }
}
inline void add2(int i,int j,ll y)//col : i+=j*y
{
    y=(y%mod+mod)%mod;
    for(int p=1;p<=n;p++)
    {
        Add(A[p][i],A[p][j]*y);
        Add(B[p][i],B[p][j]*y);
    }
}
inline void push1(int i)
{
    for(int j=1;j<=n;j++) if(j!=i&&B[j][i]) add1(j,i,-B[j][i]);
}
inline void run(int sta)
{
    ans0[sta]=ans1[sta]=0;
    memset(A,0,sizeof(A));
    memset(B,0,sizeof(B));

    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(c[i][j]!=-1)
    {
        if((sta>>c[i][j])&1) Add(A[i][j],V[i][j]);
        if((sta>>((c[i][j]+1)%k))&1) Add(B[i][j],V[i][j]);
        if((sta>>((c[i][j]+k-1)%k))&1) Add(B[i][j],V[i][j]);
    }

    ll v=1;int cnt=0;
    //step 1
    for(int i=1;i<=n;i++)
    {
        while(true)
        {
            int w=-1;
            for(int j=n;j>=i;j--) if(B[i][j]) w=j;
            if(w!=-1)
            {
                if(w>i) add2(i,w,1);
                break;
            }
            cnt++;if(cnt>n) return ;
            for(int j=1;j<=n;j++) B[i][j]=A[i][j],A[i][j]=0;
            for(int j=1;j<i;j++) push1(j);
            continue;
        }
        ll num=qow(B[i][i],mod-2);v=v*B[i][i]%mod;
        for(int j=1;j<=n;j++) A[i][j]=A[i][j]*num%mod,B[i][j]=B[i][j]*num%mod;
        push1(i);
    }
    //step 2
    for(int i=1;i<n;i++)//考虑第 i 列
    {
        int w=-1;
        for(int j=n;j>i;j--) if(A[j][i]) w=j;
        if(w==-1) continue;
        if(w!=i+1) add1(i+1,w,1),add2(w,i+1,-1);
        // 消去 >=i+2 行中第 i 列的常数项
        ll num=qow(A[i+1][i],mod-2);
        for(int j=i+2;j<=n;j++)
        {
            ll v=A[j][i]*num%mod;
            add1(j,i+1,-v);
            add2(i+1,j,v);
        }
    }
    //step 3
    memset(dp,0,sizeof(dp)),dp[0][0]=v;
    for(int i=1;i<=n;i++)
    {
        for(int p=1;p<=n;p++) dp[i][p]=dp[i-1][p-1];
        for(int l=1;l<=i;l++)
        {
            ll V=A[l][i];if((i-l)&1) V=mod-V;
            for(int j=l;j<i;j++) (V*=A[j+1][j])%=mod;
            for(int p=0;p<=n;p++) Add(dp[i][p],dp[l-1][p]*V);
        }
    }
    ans0[sta]=dp[n][cnt],ans1[sta]=cnt<n?dp[n][cnt+1]:0;
}
inline void solve()
{
    n=read(),m=read(),k=read();
    memset(c,-1,sizeof(c));
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read();
        c[u][v]=read()-1;
        V[u][v]=_rand()%mod;
    }

    for(int i=1;i<(1<<k);i++) run(i);
    for(int i=0;i<k;i++) for(int j=0;j<(1<<k);j++) if((j>>i)&1)
    {
        Add(ans0[j],mod-ans0[j^(1<<i)]);
        Add(ans1[j],mod-ans1[j^(1<<i)]);
    }
    for(int i=0;i<(1<<k);i++) printf("%d",(bool)(ans0[i]|ans1[i]));
    putchar('\n');
}
int main()
{
    int T=read();
    while(T--) solve();
    return 0;
}