自动搬运

查看原文

来自洛谷，原作者为

	Argon_Cube So now I am trapped in my Eternal Subconscienc∃.

搬运于2025-08-24 22:53:35，当前版本为作者最后更新于2024-01-02 21:24:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

不需要限制对于所有边 $i\to j$ 满足 $i<j$ 的做法。

先考虑如果已知邻接矩阵 $A$ 能不能对于每一对 $(i,j)$ 求出 $i$ 到 $j$ 的路径条数奇偶性，我们记为 $f_{i,j}$，在题目中已经给出。可以发现，我们令 $f_{i,i}=1$，则

$$f_{i,j}=\sum_{k\to j}f_{i,k}=\sum_{k}f_{i,k}a_{k,j}(i\neq j)\implies F=FA+I\implies A=I-F^{-1} $$

矩阵求逆即可。（同时请教一个问题： $F$ 不存在逆是否等价于原图不是 DAG？）

#include <algorithm>
#include <iostream>
#include <vector>
#include <bitset>
#include <string>
#include <array>

using namespace std;

array<bitset<1500>,750> matrix;

int main(int argc,char* argv[],char* envp[])
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int cnt;
    cin>>cnt;
    for(int i=0;i<cnt;matrix[i].set(i),matrix[i].set(i+cnt),i++)
        for(int j=i+1;j<cnt;j++)
        {
            char tmp;
            cin>>tmp;
            matrix[i][j]=tmp-'0';
        }
    for(int i=0;i<cnt;i++)
        for(int j=0;j<i;j++)
            if(matrix[j][i])
                matrix[j]^=matrix[i];
    int answer=0;
    for(int i=0;i<cnt;i++)
        for(int j=i+1;j<cnt;j++)
            answer+=matrix[i][j+cnt];
    cout<<answer;
    return 0;
}

场上在想能不能直接递推，以为 Gold 不会那么简单。原来是我想复杂了。