题目描述

题解

可以发现一条合法路径上必然存在边a->b使得边上的串中存在子串ab

证明考虑K>=1时一定有，然后再随便移一下

第一问直接从有子串ab的边往左右扩展找即可，把找到的称作B类路径

定义A类路径类似a->b->c->d使得点集为abc，找的话从一条a->b边满足边权为....a的开始即可

C类串就是a->b->c->d使得点集为bcd的

找出来的都是极小的串，因此当K>=1一条合法路径一定能被表示成AAAABCCCC的形式，其中A和C可有可无，直接dp即可

当K=0时可能有空边，那么就是ABC_ABC_ABC的形式，做法一样

设f[0/1][i][j]表示结尾是 A/空 或 结尾是 B/C，长度为i末尾为j的方案

把可以转移的放到g[0/1/2][i][j][k]中，表示为A/B/C类串，长i首位jk

然后可以n^4

code

#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define add(a,b) a=((a)+(b))%1000000007
#define mod 1000000007
#define ll long long
#define file
using namespace std;

int b[51][51][51],c[51][51],d1[10001],d2[10001],n,m,i,j,k,l,x,h,t1,t2;
ll f[2][101][51],g[3][101][51][51],ans[101];
bool a[51][51],Ans1;

void work1()
{
	int i,j,k,l,x,len;
	
	fo(i,1,n)
	{
		fo(j,1,n)
		if (a[i][j] && c[i][j])
		{
			fo(k,1,c[i][j]-1) //B
			if (b[i][j][k]==i && b[i][j][k+1]==j)
			{
				x=i;h=t1=1;d1[1]=i;len=1;
				fd(l,k-1,1) d1[++t1]=b[i][j][l],++len;
				while (h<t1)
				{
					++h;
					if (len>n+n || !a[d1[h]][x]) {h=-114514;break;}
					fd(l,c[d1[h]][x],1) d1[++t1]=b[d1[h]][x][l],++len;
					x=d1[h];
				}
				if (h<t1) break;
				
				x=j;h=t2=1;d2[1]=j;
				fo(l,k+2,c[i][j]) d2[++t2]=b[i][j][l],++len;
				while (h<t2)
				{
					++h;
					if (len>n+n || !a[x][d2[h]]) {h=-114514;break;}
					fo(l,1,c[x][d2[h]]) d2[++t2]=b[x][d2[h]][l],++len;
					x=d2[h];
				}
				if (h<t2) break;
				
				if (!Ans1)
				{
					Ans1=1;
					printf("%d\n",len+1);
					fd(l,t1,1) printf("%d ",d1[l]);
					fo(l,1,t2) printf("%d ",d2[l]);
					printf("\n");
				}
				++g[1][len][d1[t1]][d2[t2]];
				break;
			}
			if (b[i][j][c[i][j]]==i) //A
			{
				x=i;h=t1=1;d1[1]=i;len=1;
				fd(l,c[i][j]-1,1) d1[++t1]=b[i][j][l],++len;
				while (h<t1)
				{
					++h;
					if (len>n+n || !a[d1[h]][x]) {h=-114514;break;}
					fd(l,c[d1[h]][x],1) d1[++t1]=b[d1[h]][x][l],++len;
					x=d1[h];
				}
				if (!(len>n+n || h<t1)) ++g[0][len][d1[t1]][j];
			}
			if (b[i][j][1]==j) //C
			{
				x=j;h=t2=1;d2[1]=j;len=1;
				fo(l,2,c[i][j]) d2[++t2]=b[i][j][l],++len;
				while (h<t2)
				{
					++h;
					if (len>n+n || !a[x][d2[h]]) {h=-114514;break;}
					fo(l,1,c[x][d2[h]]) d2[++t2]=b[x][d2[h]][l],++len;
					x=d2[h];
				}
				if (!(len>n+n || h<t2)) ++g[2][len][i][d2[t2]];
			}
		}
	}
}
void work2()
{
	int i,s,j,k,l;
	
	fo(i,1,n)
	{
		fo(j,1,n)
		{
			fo(k,1,n+n)
			add(f[0][k][j],g[0][k][i][j]),add(f[1][k][j],g[1][k][i][j]);
		}
	}
	fo(i,1,n+n-1)
	{
		fo(s,0,1)
		{
			fo(j,1,n)
			if (f[s][i][j])
			{
				if (s==1)
				{
					fo(l,1,n)
					if (a[j][l] && !c[j][l])
					add(f[0][i+1][l],f[s][i][j]);
				}
				fo(k,1,n+n-i)
				{
					fo(l,1,n)
					switch (s)
					{
						case 0:{
							add(f[0][i+k][l],f[s][i][j]*g[0][k][j][l]);
							add(f[1][i+k][l],f[s][i][j]*g[1][k][j][l]);
							break;
						}
						case 1:{
							add(f[1][i+k][l],f[s][i][j]*g[2][k][j][l]);
							break;
						}
					}
				}
			}
		}
	}
}

int main()
{
	freopen("path.in","r",stdin);
	#ifdef file
	freopen("path.out","w",stdout);
	#endif
	
	scanf("%d%d",&n,&m);
	fo(i,1,m)
	{
		scanf("%d%d",&j,&k);a[j][k]=1;
		scanf("%d",&c[j][k]);
		fo(l,1,c[j][k]) scanf("%d",&b[j][k][l]);
	}
	
	work1();
	if (!Ans1)
	{
		printf("0\n");
		printf("\n");
		fo(i,1,n+n) printf("0\n");
	}
	else
	{
		work2();
		fo(i,1,n+n) fo(j,1,n) add(ans[i],f[1][i][j]);
		fo(i,1,n+n) printf("%lld\n",ans[i]);
	}
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}

6680. 【2020.06.02省选模拟】路

原文：https://www.cnblogs.com/gmh77/p/13040000.html