星星罐子

题目描述

十一年后，这千颗写满字句的纸星星终于得以见光。

LCT从罐子中取出N颗星星，并将它们一一展开。

小戾很紧张。

他的LCT是个有一套独特行事风格的人。就好比度量思念这件事。

他知道，LCT会将取出的这N颗星星上的字句按照某种顺序连接成一条更长的字条。在这条拼成的字条当中，他会下意识地去寻找自己的名字，即L,C,T的出现位置。他若是看到相邻的两次出现相距很远，便会生出一些焦虑。具体而言，假设拼成的字条长度为|S|，且其中所有包含字符L,C,T的下标组成有序序列\(p_1,p_2,\cdots,p_k\)，\(1≤p_{i?1}。那么LCT看完这些之后的心情郁闷程度就可以表示为：

如果只出现了一次或是没有出现，这个郁闷程度就被定义为0。

小戾想要知道，所有的连接顺序会给LCT带来的郁闷程度之和是多少。由于这个值可能会很大，你只需要输出它对\(10^9+7\)取模后的结果。两个连接顺序被认为是不同的，当且仅当存在一个星星的出现位置在新的字条中不一样。

输入格式
第一行一个数\(N\)，表示LCT取出的星星数量。

接下来N行，每行一个字符串，表示第i颗星星上的字句。保证字符串只由大小写英文字母构成。而只有大写的L、C、T才计入LCT名字的出现序列。

输出格式
一行，一个数表示所有连接顺序给LCT带来的郁闷程度之和模109+7后的值。

样例输入1

2
LB
TDTW

样例输出1

16

样例输入2

5
TC
KTATO
CAU
RTK
OC

样例输出2

3768

题目限制
时间限制：1000ms

空间限制：512MB

对于50%的数据，\(N≤5\), 每个字符串长度\(≤10\)。

对于100%的数据，\(N≤10\), 每个字符串长度\(≤10^4\)。保证字符串只由大小写英文字母构成。

最暴力的方法当然是直接暴力枚举排列，然后暴力求这种排列下的郁闷程度，然后相加。复杂度\(O(n!*|s|)\)

肯定会超时，瓶颈在计算郁闷程度（排列的复杂度很难优化）。所以我们考虑边算排列边计算郁闷程度。

首先可以预处理出一个星星内部的郁闷程度\(s\)，还有他开头到最前面的LCT的距离，最后面的LCT到结尾的距离。然后在搜索中，上一个星星的最后LCT到结尾的距离加上这一颗星星第一个LCT到开头的距离就是一段，答案也要加上这一段的平方。

有几个特殊情况：首先如果一个星星没有LCT，那么把上一个的距离直接加上这一段的长度。如果这个星星是第一个星星，那么就不用加上最前面的LCT到上一个星星最后一个LCT的距离了。

#include
#include
const int N=15,M=1e5+5,mod=1e9+7;
struct node{
	int s,l,r,len;
}d[N];
char s[M];
int n,ans,v[N],lst;
void dfs(int x,int l,int s)
{
	if(x>n)
	{
		ans=(ans+s)%mod;
		return;
	}
	for(int i=1;i<=n;i++)
	{
		if(!v[i])
		{
			v[i]=1;
			if(!l) 
				dfs(x+1,d[i].r,s+d[i].s);
			else if(!d[i].l)
				dfs(x+1,l+d[i].len,s);
			else
				dfs(x+1,d[i].r,(1LL*(d[i].l+l-1)*(d[i].l+l-1)%mod+1LL*d[i].s+s)%mod);
			v[i]=0;
		}
	}
	
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s+1),d[i].len=strlen(s+1);
		lst=0;
		for(int j=1;j<=d[i].len;j++)
		{
			if(s[j]=='L'||s[j]=='C'||s[j]=='T')
			{
				if(!lst)
					d[i].l=j;
				else 
					d[i].s=(d[i].s+1LL*(j-lst)*(j-lst))%mod;
				lst=j;
			}
		}
		if(lst)
			d[i].r=d[i].len-lst+1;		
	}
	dfs(1,0,0);
	printf("%d",ans);
	return 0;
}