题意简述

给定一幅有向图 $G=(V,E),|V|\le 400 ,|E|\le 400$ ，保证所有边由编号小的点指向编号大的点（即 $\forall (u,v)\in E,u<v$ ），每条边权值 $w\in\{0,1\}$。

定义一种权值分配方案是好的，当且仅当对于每一对 $(u,v)$，都有 $(u,v)$ 间的所有路径上的所有边异或和相等。

求出好的权值分配方案数，对 $(10^9+7)$ 取模。

题解

将 $m$ 条边的权值视为未知数，记第 $i$ 条边的权值为 $x_i$ ，则原题对于好的权值分配方案的限制等价于给出了一个异或方程组。

异或运算就是模 $2$ 意义下的加法，具有良好的性质，是线性的。

线性方程组

对于线性方程组，我们小学二年级就学过这么一个性质：

如果要解出 $n$ 个未知数，至少要 $n$ 个方程构成的方程组

为什么是至少，因为方程之间可能出现线性相关的情况，换言之，方程之间可以互相表示，那么就存在“废话方程”。

也有以下严谨表述：

如果要解出 $n$ 个未知数，需要 $n$ 个线性无关的方程构成的方程组

并且，含有 $n$ 个未知数的线性方程组最多有 $n$ 个线性无关的方程。

这是一个充要条件：$n$ 个线性无关的方程构成的方程组一定能解出 $n$ 个未知数

于是对于原题，我们只要找到所有线性异或方程构成的方程组的秩（rank）就好了。

这里补充一点芝士。

线性代数最初就是研究线性方程的。

一个齐次的线性方程组可以用一个矩阵来表达。

所以一个矩阵就等价于一个线性方程组。

一个矩阵的秩其实就是：

百度百科：

在线性代数中，一个矩阵A的列秩是A的线性独立的纵列的极大数目。类似地，行秩是A的线性无关的横行的极大数目。即如果把矩阵看成一个个行向量或者列向量，秩就是这些行向量或者列向量的秩，也就是极大无关组中所含向量的个数。

定理：矩阵的行秩，列秩，秩都相等。

很好够了。

$m$ 个变量，如果有 $c$ 个线性无关的方程组约束他们，那么只要确定了其中的 $m-c$ 个自由元，剩下 $c$ 个主元可以由线性方程则解出来。

每个变量两种取值，一共有 $2^{m-c}$ 方案。

于是我们只需要求有多少个线性无关的方程组即可。

我们发现化简移项后的异或方程种每个变量要么出现一次，要么不出现，所以可以用 $bitset$ 把一个异或方程记作一个二进制数，通过求这些二进制数的线性基的大小（线性基就是一组线性无关的极大向量集合），即为线性方程组的秩。

但我们发现一幅有向图上的方程实在太多了，我们要想一个办法去少枚举线性相关的方程，但不要把方程组的秩算小了就好。

我们发现重复路径有点像环，我们可以通过dfs解决。非dfs树上的边一定对应着一个新的路径。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9+7;
int qp(int x,int b){
    int ret = 1;
    for(;b;b>>=1){
        if(b&1)ret*=x,ret%=mod;
        x*=x,x%=mod;
    }
    return ret;
}
const int N = 405;
int n,m;
vector<pair<int,int> >G[N];
int d[N];
bitset<N>b[N];
bitset<N>e[N];
int tot;
void insert(bitset<N>x){
    for(int i=tot;i>=0;i--){
        if(!x[i])continue;
        if(e[i].any()){
            x ^= e[i];
        }else{
            e[i] = x;
            break;
        }
    }
}
bool vis[N];
void dfs(int u){
    vis[u] = 1;
    for(auto v:G[u]){
        auto r = b[u];
        r.flip(v.second);
        if(vis[v.first]){
            r ^= b[v.first];
            insert(r);
        }else{
            b[v.first] = r;
            dfs(v.first);
        }
    }
}
void solve(){
    cin>>n>>m;
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        G[u].push_back({v,tot++});
        d[v]++;
    }
    tot--;
    for(int i=1;i<=n;i++){
        if(d[i])continue;
        memset(vis,0,sizeof(vis));
        dfs(i);
    }
    int ans = 0;
    for(int i=0;i<=tot;i++){
        if(e[i].any())ans ++;
    }
    cout<<qp(2,m-ans);
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int aqx = 1;
    while(aqx--)solve();
    return 0;
}