Wannafly挑战赛9: B. 数一数-白红宇

Wannafly挑战赛9: B. 数一数

阅读量：2144 次

发布时间：2019-04-30

本文共 2051 字，大约阅读时间需要 6 分钟。

链接：

来源：牛客网

题目描述

设s,t为两个字符串，定义f(s,t) = t的子串中，与s相等的串的个数。如f("ac","acacac")=3, f("bab","babab")=2。现在给出n个字符串，第i个字符串为s

_i。你需要对

$\forall 1 \leq i \leq n$ ，求出

$\prod_{j=1}^n {f(s_i,s_j)}$ ，由于答案很大，你只需要输出对 998244353取模后的结果。

输入描述:

第一行一个整数n。接下来n行每行一个仅由英文字母构成的非空字符串，第i个字符串代表si。

输出描述:

共n行，第i行输出对 998244353取模的结果。

对于对于字符串s和t，当前仅当s==t时f(s, t)和f(t, s)都为1，否则一定有一个是0

答案求的是连乘，所以一旦某个f(s, t)是0，那么最后串s的答案就一定为0

对于num个完全相同的串s，可以把它们缩成1个，这样若f(t, s)==x，那么s对t的贡献就是x^num

去重后每计算一个f(s, t)都一定会得出一个串的答案（为0）所以最后复杂度为O(len+n)

#include
   
    #include
    
     #include
     
      #include
      using namespace std;map
       
         p;#define mod 998244353#define LL long longLL ans[1000005];int net[2000005], id[1000005];typedef struct{	int len, sum;	char *str;}Str;Str s[1000005];char str[2000005];LL Pow(LL a, LL b){	LL ans = 1;	while(b)	{		if(b%2)			ans = ans*a%mod;		a = a*a%mod;		b /= 2;	}	return ans;}int Kmp(char *b, char *a){	int i, j, n, m, ans;	i = j = 1, ans = 0;	n = strlen(a+1);	m = strlen(b+1);	while(i<=n)	{		if(a[i]==b[j])		{			if(j==m)			{				ans++;				j = net[j+1];				i++;			}			else				i++, j++;		}		else		{			j = net[j];			if(j==0)				i++, j = 1;		}	}	return ans;}int Getnext(char *b, char *a){	int i, j, m;	i = 1, j = 0;	net[1] = 0;	m = strlen(b+1);	while(i<=m)	{		if(j==0 || b[i]==b[j])		{			i++, j++;			if(b[i]==b[j])				net[i] = net[j];			else				net[i] = j;		}		else			j = net[j];	}	return Kmp(b, a);}int main(void){	int n, i, j, now;	scanf("%d", &n);	for(i=1;i<=n;i++)	{		scanf("%s", str+1);		if(p.count(str+1))		{			id[i] = p[str+1];			s[id[i]].sum++;			continue;		}		p[str+1] = i;		s[i].sum = 1;		s[i].len = strlen(str+1);		s[i].str = new char[s[i].len+5];		strcpy(s[i].str+1, str+1);	}	for(i=1;i<=n;i++)		ans[i] = 1;	for(i=1;i<=n;i++)	{		if(ans[i]==0 || id[i])			continue;		for(j=1;j<=n;j++)		{			if(i==j || id[j])				continue;			now = Getnext(s[i].str, s[j].str);			if(now==0)			{				ans[i] = 0;				break;			}			else			{				ans[j] = 0;				ans[i] = ans[i]*Pow(now, s[j].sum)%mod;			}		}	}	for(i=1;i<=n;i++)	{		if(id[i]!=0)			printf("%lld\n", ans[id[i]]);		else			printf("%lld\n", ans[i]);	}	return 0;}/*5aaaaaaa*/