Solution:P9980([USACO23DEC] Flight Routes G)

不需要限制对于所有边 $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？） ```cpp #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 不会那么简单。原来是我想复杂了。