Solution:P9980([USACO23DEC] Flight Routes G)

Argon_Cube · 2024-01-02 21:24:24 · 题解

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

先考虑如果已知邻接矩阵 A 能不能对于每一对 (i,j) 求出 i 到 j 的路径条数奇偶性，我们记为 f_{i,j}，在题目中已经给出。可以发现，我们令 f_{i,i}=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 不会那么简单。原来是我想复杂了。