Codeforces 781D Axel and Marston in Bitland 矩阵 bitset

原文链接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;
}

  

上一篇:Bumped! 2017 ICPC North American Qualifier Contest (分层建图+dijstra)


下一篇:R 语言安装