原文链接https://www.cnblogs.com/zhouzhendong/p/CF781D.html
题目传送门 - CF781D
题意
有一个 n 个点的图，有 m 条有向边，边有两种类型：0 和 1 。
有一个序列，其构造方案为：初始情况为 0 ；对于当前串，将当前串的 0 变成 1 ，1 变成 0 ，接到当前串的后面，得到一个新串；不断进行这个操作。
最终得到一个形如 0110100110010110…… 的无限串。
问从节点 1 出发，依次经过上述串对应的 0/1 边，最多能走多少步。
如果答案大于 $10^{18}$ ，输出 -1 。
$n\leq 500,m\leq 2n^2$
题解
首先考虑处理出两个矩阵，分别处理 0/1 两种类型的边的转移。
于是我们可以直接矩阵倍增一下得到一个 $O(n^3 \log 10^{18})$ 的做法。
再注意到我们只关系这些矩阵元素是否为 0 ，那么我们只需要用 bitset 优化一下矩阵乘法就好了。
时间复杂度 $O(n^3 \log 10^{18} / 32)$ 。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL read(){
LL x=0,f=1;
char ch=getchar();
while (!isdigit(ch)&&ch!='-')
ch=getchar();
if (ch=='-')
f=-1,ch=getchar();
while (isdigit(ch))
x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x*f;
}
const int N=505;
const LL INF=1000000000000000000LL;
int n,m;
struct Mat{
bitset <N> v[N];
Mat(){}
Mat(int x){
for (int i=1;i<=n;i++)
v[i].reset();
for (int i=1;i<=n;i++)
v[i][i]=x;
}
friend Mat operator * (Mat a,Mat b){
Mat ans(0);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (a.v[i][j])
ans.v[i]|=b.v[j];
return ans;
}
}M[2][35];
int main(){
n=read(),m=read();
M[0][0]=M[1][0]=Mat(0);
for (int i=1;i<=m;i++){
int a=read(),b=read(),t=read();
M[t][0].v[a][b]=1;
}
int k=0;
while (M[0][k].v[1].count()&&(1LL<<(k<<1))<=INF){
k++;
M[0][k]=M[0][k-1]*M[1][k-1]*M[1][k-1]*M[0][k-1];
M[1][k]=M[1][k-1]*M[0][k-1]*M[0][k-1]*M[1][k-1];
}
LL s=0,p=0;
Mat now(0);
now.v[1][1]=1;
while (k>0&&s<=INF){
k--;
if ((now*M[p][k]).v[1].count()){
now=now*M[p][k];
s+=1LL<<(k<<1);
p^=1;
if ((now*M[p][k]).v[1].count()){
now=now*M[p][k];
s+=1LL<<(k<<1);
if ((now*M[p][k]).v[1].count()){
now=now*M[p][k];
s+=1LL<<(k<<1);
p^=1;
}
}
}
}
if (s>INF)
puts("-1");
else
cout << s << endl;
return 0;
}