QOJ61 Cut Cut Cut! 题解

题面。

题解

假设 \(1\) 号点有 \(d\) 条出边，给 \(d\) 条出边赋 \(d\) 个独立的单位向量，接下来，每个出边记作入边的随机线性组合，那么对于第 \(i\) 个点，答案就是入边生成的线性空间的秩。

正确性证明：

对于每个点考虑，假设现在考虑 \(i\) 号点，将其入边集合记作 \(E1_{i}\) ，出边集合记作 \(E2_i\) ，对于所有的 \(e1\in E1,e2\in E2\)，有一个随机变量 \(val_{e1,e2}\) 表示 \(e1\) 这条入边在 \(e2\) 这条出边里组合的系数（先将其视为未知数。）。

假设 \(i\) 的答案为 \(k\) ，那么只需要证明 \(i\) 处入边构成的多项式矩阵的秩是 \(k\) ，这样用 \(Schwartz-Zippel\) 引理就知道每个元代随机值的情况下也有 \(1-(d/mod)\) 的概率秩为 \(k\) ，\(d\) 为多项式次数， \(mod\) 为选取的大素数模数。

在本题中，这个多项式矩阵的次数不超过 \(n\) ，那么用来测试秩是否为 \(k\) 的多项式次数不超过 \(20n\) ，因此选取的 \(mod\) 只要远大于 \(20n\) 即可保证正确率较高，那么根据\(Schwartz-Zippel\) 引理，我们可以随机赋权（赋那个组合的系数。）。

秩小于等于最小割是显然的，证明考虑入边的向量肯定是割边的向量的线性组合，那秩不能超过割边的个数。

再证秩大于等于最大流，假设最大流为 \(k1\) ，假设最大流上这些随机变量赋成 \(1\) ，其他的赋成 \(0\) ，那么矩阵就只剩下 \(k1\) 个位置是 \(1\) 了，而且刚好不同行不同列，所以此时秩为 \(k1\) 。而多项式矩阵存在一种赋值方法使其秩为 \(k1\) ，那么原本的秩必然大于等于 \(k1\) ，因为原本线性相关的项赋值后也必然线性相关。

那么根据最小割最大流定理，有 \(k=k1\) ，所以秩，最小割，最大流均相等。

代码

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=(l);i<=(r);++i)
#define ReFor(i,r,l) for(int i=(r);i>=(l);--i)
const int N=100010;
const int mod=1000000007;
typedef long long ll;
using namespace std;
int n,m,out_deg_1;
vector<int> G[N];
mt19937_64 rnd(20070810);
ll qpow(ll a,int b)
{
    ll res=1;
    while(b)
    {
        if(b&1)(res*=a)%=mod;
        (a*=a)%=mod;b>>=1;
    }
    return res;
}
template<typename T1,typename T2>
void Add(T1 &a,T2 b){a+=b;if(a>=mod)a-=mod;return;}
template<typename T1,typename T2>
void Sub(T1 &a,T2 b){a-=b;if(a<0)a+=mod;return;}
struct Linear_Basis
{
    vector<ll> vec[21];
    void clear(){For(i,0,out_deg_1-1)vec[i].clear();return;}
    void init(){For(i,0,out_deg_1-1)vec[i].resize(out_deg_1);return;}
    void insert(vector<ll> a)
    {
        ReFor(i,out_deg_1-1,0)
        {
            if(a[i]==0)continue;
            if(vec[i][i]!=0)
            {
                ll _=a[i];
                For(j,0,i){ll delta=_;(delta*=vec[i][j])%=mod;Sub(a[j],delta);}
                continue;
            }
            else if(vec[i][i]==0)
            {
                ll inv_a_i=qpow(a[i],(mod-2));
                For(j,0,i)(a[j]*=inv_a_i)%=mod;
                For(j,0,i)vec[i][j]=a[j];return;
            }
        }
        return;
    }
    int get_rank(){int res=0;For(i,0,out_deg_1-1)res+=vec[i][i];return res;}
}a[N];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    For(i,1,m){int x,y;cin>>x>>y;G[x].emplace_back(y);}
    {
        out_deg_1=0;for(auto y:G[1])++out_deg_1;For(i,1,n){a[i].clear();a[i].init();}For(i,0,out_deg_1-1)a[1].vec[i][i]=1; 
    };
    For(i,1,n)
    {
        for(auto y:G[i])
        {
            vector<ll> tmp;tmp.clear();tmp.resize(out_deg_1);
            For(j,0,out_deg_1-1)
            {
                ll rnd_val=(rnd()%mod);if(rnd_val<0)rnd_val+=mod;
                For(k,0,out_deg_1-1){ll delta=rnd_val;(delta*=a[i].vec[j][k])%=mod;Add(tmp[k],delta);}
            }
            a[y].insert(tmp);
        }
    }
    For(i,2,n){int ans_i=a[i].get_rank();cout<<ans_i<<" ";}return 0;
}