CF331E2 Deja Vu 图论

题意:

戳这里

分析:

考场上只会暴搜/kk

  • 正解:

首先 \(n\) 很小,所以我们理论上来说可以处理出任意相邻两点之间的路径,然后通过拼接得到任意一个点对之间的答案,那么我们开始考虑如何进行拼接,首先暴力拼接显然不可取,所以我们可以只记录一些有用的状态

由于每条路径都有起点和终点,这不是废话么 ,所以我们可以将 \(u\to v\) 的路径分成四类

  1. 路径序列比顶点序列的少了一个 \(v\)

  2. 路径序列和顶点序列相同

  3. 路径序列比顶点序列的少了一个 \(u\)

  4. 其余情况

我们发现第三类的边没法转移,但是前三类的边可能存在拼接的方式形成,所以我们设转移状态为 \(f_{flag,u,len}\) 表示第 \(flag\) 类边 , 终点为 \(u\) , 长度(边数)为 \(len\)的方案数

初始状态就是 \(f_{0,u,0}=1\) ,答案就是 \(\displaystyle \sum_{i=0}^n\sum_{len=1}^{2n}f_{1,i,len}\)

好,设出转移状态之后我们开始考虑如何转移

  • 状态 0 \(\to\) 状态 0

    就是在一个 \(0\) 状态的边后面再接一个 \(0\) 状态的边,\(f_{0,u,l}\to f_{0,v,l+len}\)

  • 状态 0 \(\to\) 状态 1

    就是在一个 \(0\) 状态的边后面再接一个 \(1\) 状态的边,\(f_{0,u,l}\to f_{1,v,l+len}\)

  • 状态 1 \(\to\) 状态 0

    就是在一个 \(1\) 状态的边后面再接一个顶点序列为空的边,\(f_{1,u,l}\to f_{0,v,l+1}\)

  • 状态 1 \(\to\) 状态 1

    就是在一个 \(1\) 状态的边后面再接一个 \(2\) 状态的边,前面接一个状态为 \(0\) 的边,\(f_{1,u,l}\to f_{1,v,l+len}\)

我们发现这种转移就像是 \(f_{flag1,u1,len}\to f_{flag2,u2,len+\Delta}\) 可以看成是一个五元组 \((flag1,flag2,u1,u2,\Delta)\) 所以我们就按照上面的转移式预处理出所有的五元组,然后按照 \(len\) 从小到大的顺序进行转移统计答案

代码:

#include<bits/stdc++.h>
#define pii pair<int,int>
#define mk(x,y) make_pair(x,y)
#define lc rt<<1
#define rc rt<<1|1
#define pb push_back
#define fir first
#define sec second
#define inl inline
#define reg register

using namespace std;

namespace zzc
{
	typedef long long ll;
	inline int read()
	{
		int x=0,f=1;char ch=getchar();
		while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
		while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
		return x*f;
	}
	
	const int maxn = 55;
	const int mod = 1e9+7;
	int n,m;
	int e[maxn][maxn],f[2][maxn][maxn<<1];
	vector<int> str[maxn][maxn],trans[2][2][maxn][maxn];
	typedef deque<int>::iterator IT;
	
	bool extend(deque<int> &q,IT it,int kind)
	{
		bool flag=true;
		if(!kind)
		{
			for(auto pre=prev(it);it!=q.begin()&&(int)q.size()<=2*n;it=pre,pre=prev(it))
			{
				flag&=e[*pre][*it];
				q.insert(q.begin(),str[*pre][*it].begin(),str[*pre][*it].end());
			}
		}
		else
		{
			for(auto nxt=next(it);nxt!=q.end()&&(int)q.size()<=2*n;it=nxt,nxt=next(it))
			{
				flag&=e[*it][*nxt];
				q.insert(q.end(),str[*it][*nxt].begin(),str[*it][*nxt].end());
			}
		}
		return flag&((int)q.size()<=2*n);
	}
	
	void init()
	{
		//0->0
		for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
		{
			if(str[i][j].size()&&str[i][j].back()==i)
			{
				deque<int> q(str[i][j].begin(),str[i][j].end());
				if(extend(q,prev(q.end()),false)) trans[0][0][q.front()][j].pb((int)q.size());
			}
		}
		
		//0->1
		for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
		{
			auto p=find(str[i][j].begin(),str[i][j].end(),i);
			if(p==str[i][j].end()||(++p)==str[i][j].end()||(*p)!=j) continue;
			deque<int> q(str[i][j].begin(),str[i][j].end());
			IT it=q.begin()+(p-str[i][j].begin())-1;
			if(extend(q,it,false)&&extend(q,it+1,true)) trans[0][1][q.front()][q.back()].pb((int)q.size()-1);
		}
		
		//1->0
		for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(e[i][j]&&str[i][j].empty()) trans[1][0][i][j].pb(1);
		
		//1->1
		for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
		{
			if(str[i][j].size()&&str[i][j].front()==j)
			{
				deque<int> q(str[i][j].begin(),str[i][j].end());
				if(extend(q,q.begin(),true)) trans[1][1][i][q.back()].pb((int)q.size());
			}
		}
		
	}
	
	void work()
	{
		int a,b,c;
		n=read();m=read();
		for(int i=1;i<=n;i++) f[0][i][0]=1;
		for(int i=1;i<=m;i++)
		{
			a=read();b=read();
			e[a][b]=1;
			c=read();
			while(c--) str[a][b].pb(read());
		}
		init();
		for(int l=0;l<2*n;l++) for(int i=0;i<=1;i++) for(int j=1;j<=n;j++)
		{
			if(f[i][j][l])
			{
				for(int x=0;x<=1;x++) for(int y=1;y<=n;y++) for(auto v:trans[i][x][j][y])
				if(v+l<=2*n) f[x][y][v+l]=(f[x][y][v+l]+f[i][j][l])%mod;
			}
		}
		for(int l=1;l<=2*n;l++)
		{
			int sum=0;
			for(int i=1;i<=n;i++) sum=(sum+f[1][i][l])%mod;
			printf("%d\n",sum);
		}
	
	}

}

int main()
{
	zzc::work();
	return 0;
}

上一篇:VUE入门学习


下一篇:codechef TREECNT2