QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#351669#8306. Boring ProblemLynkcatRE 1ms5656kbC++204.0kb2024-03-12 10:52:252024-03-12 10:52:27

Judging History

你现在查看的是最新测评结果

  • [2024-03-12 10:52:27]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:5656kb
  • [2024-03-12 10:52:25]
  • 提交

answer

#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define sz(x) ((int)((x).size()))
#define int ll
// #define N 
using namespace std;
const int N=205;
int cnt;
int n,m,K;
int son[N*N][26],tr[N*N][26];
int rt;
poly G[N*N];
int fail[N*N];
int p[26];
int id[N*N],tot;
int ans[N];
poly f[N*N];
vector<poly>all;
const int mod=1000000007;
poly operator+(poly x,poly y)
{
	poly res(sz(x),0);
	for (int i=0;i<sz(x);i++) res[i]=(res[i]+x[i])%mod;
	for (int i=0;i<sz(y);i++) res[i]=(res[i]+y[i])%mod;
	return res;
}
poly operator-(poly x,poly y)
{
	poly res(sz(x),0);
	for (int i=0;i<sz(x);i++) res[i]=(res[i]+x[i])%mod;
	for (int i=0;i<sz(y);i++) res[i]=(res[i]-y[i]+mod)%mod;
	return res;
}
poly operator*(poly x,int y)
{
	for (auto &u:x) u=u*y%mod;
	return x;
}
inline ll quickPower(ll x,ll y)
{
	ll res=1;
	while (y)
	{
		if (y&1) res=res*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return res;
}
void ins(int &k,int dep,string &s)
{
	if (!k) k=++cnt;
	// cout<<"ins "<<k<<endl;
	if (dep==m)
		return;
	if (!son[k][s[dep]-'a'])
	{
		G[k].push_back(s[dep]-'a');
	}
	// cout<<"walk "<<s[dep]-'a'<<endl;
	ins(son[k][s[dep]-'a'],dep+1,s);
	for (int i=1;i<sz(G[k]);i++)
	{
		if (id[son[k][G[k][i]]]) continue;
		id[son[k][G[k][i]]]=++tot;
	}
}
void workon(int k)
{
	if (G[k].empty()) 
	{
		all.push_back(f[k]);
		return;
	}
	poly now=f[k];
	now.back()=(now.back()+mod-1)%mod;
	for (int i=0;i<K;i++)
		if (i!=G[k][0])
		{
			now=now-f[tr[k][i]]*p[i];
		}
	now=now*quickPower(p[G[k][0]],mod-2);
	f[son[k][G[k][0]]]=now;
}
void BellaKira()
{
	cin>>n>>m>>K;
	for (int i=0;i<K;i++)
	{
		int x;
		cin>>x;
		p[i]=x*quickPower(100,mod-2)%mod;
	}
	for (int i=1;i<=n;i++)
	{
		string st;
		cin>>st;
		ins(rt,0,st);
	}
	id[rt]=++tot;
	queue<int>q;
	for (int i=0;i<K;i++) tr[0][i]=1;
	q.push(rt);
	while (!q.empty())
	{
		int u=q.front();
		q.pop();
		for (int i=0;i<K;i++)
			if (son[u][i])
				tr[u][i]=son[u][i],fail[son[u][i]]=tr[fail[u]][i],q.push(son[u][i]);
			else tr[u][i]=tr[fail[u]][i];
	}
	for (int i=1;i<=cnt;i++) f[i].resize(tot+1);
	for (int i=1;i<=cnt;i++)
		if (id[i]) f[i][id[i]-1]=1;
	q.push(rt);
	while (!q.empty())
	{
		int u=q.front();
		q.pop();
		workon(u);
		for (int i=0;i<K;i++)
			if (son[u][i]) q.push(son[u][i]);
	}
	// for (int i=0;i<tot;i++)
	// {
	// 	for (int j=0;j<=tot;j++) cout<<all[i][j]<<" ";
	// 	cout<<endl;
	// // }
	// cout<<endl;
	// return;
	for (int i=0;i<tot;i++)
	{
		if (!all[i][i])
		{
			for (int j=i;j<tot;j++)
				if (all[j][i])
				{
					swap(all[i],all[j]);
					break;
				}
		}
		assert(all[i][i]);
		int t=quickPower(all[i][i],mod-2);
		for (int j=i;j<=tot;j++)
			all[i][j]=all[i][j]*t%mod;
		for (int j=i+1;j<tot;j++)
		{
			int op=all[j][i];
			for (int k=0;k<=tot;k++)
				all[j][k]=(all[j][k]-op*all[i][k]%mod+mod)%mod;
		}
		for (int j=0;j<i;j++)
		{
			int op=all[j][i];
			for (int k=0;k<=tot;k++)
				all[j][k]=(all[j][k]-op*all[i][k]%mod+mod)%mod;
		}
	}

	// for (int i=0;i<tot;i++)
	// {
	// 	for (int j=0;j<=tot;j++) cout<<all[i][j]<<" ";
	// 	cout<<endl;
	// }
	// cout<<endl;

	for (int i=1;i<=cnt;i++)
	{
		for (int j=0;j<tot;j++)
			ans[i]=(ans[i]+f[i][j]*(mod-all[j].back())%mod)%mod;
		ans[i]=(ans[i]+f[i].back())%mod;
		if (G[i].empty()) assert(ans[i]==0);
	}
	for (int i=1;i<=cnt;i++)
		if (ans[i]!=0)
		{
			int op=1;
			for (int j=0;j<K;j++)
				op=(op+ans[tr[i][j]]*p[j]%mod)%mod;
			assert(ans[i]==op);
		}

	int now=1;
	string st;
	cin>>st;
	int tt=0;
	for (auto u:st)
	{
		tt++;
		if (ans[now])
			now=tr[now][u-'a'];
		cout<<(ans[now]+tt)%mod<<'\n';
	}
}
signed main()
{
	IOS;
	cin.tie(0);
	int T=1;
	while (T--)
	{
		BellaKira();
	}
}
/*list:
1.mod 998244353 or 1e9+7 or ???
2.N
3.duipai shuju xingtai duoyidian
...
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5656kb

input:

2 2 2
50 50
aa
bb
ababaa

output:

3
4
5
6
7
6

result:

ok 6 numbers

Test #2:

score: 0
Accepted
time: 1ms
memory: 3620kb

input:

3 3 3
25 25 50
abc
bac
cab
ababbabbcaaa

output:

13
333333343
333333344
333333345
17
333333347
333333348
20
333333358
666666692
23
24

result:

ok 12 numbers

Test #3:

score: 0
Accepted
time: 1ms
memory: 3516kb

input:

4 4 4
10 20 30 40
abcb
cabc
abbb
cccc
ababacabaabcca

output:

146386692
32395942
146386694
32395944
146386696
851050282
242422295
512573933
146386700
146386701
32395951
66073407
572924730
242422302

result:

ok 14 numbers

Test #4:

score: 0
Accepted
time: 1ms
memory: 5600kb

input:

2 2 2
50 50
aa
aa
bb

output:

7
8

result:

ok 2 number(s): "7 8"

Test #5:

score: 0
Accepted
time: 1ms
memory: 5620kb

input:

2 3 3
25 25 50
abc
bac
abcababababab

output:

15
8
3
4
5
6
7
8
9
10
11
12
13

result:

ok 13 numbers

Test #6:

score: -100
Runtime Error

input:

1 4457 3
37 22 41
acbaccbbbccabccabbbbccaacabbabcbcccaabcccaaabcbaaaabbbcbcaccbbabcabbaabbcaaccbbbcbcbbacacbbaabacacbbabacababbbacacbacbccacbbcccaaccbabccbbccacbaccaccbcccbbcbacacbbcbacbacacbacbbcccccaababaccbabaccaaccbcacbccccbcbaccacccaacbbaccbcacbbaaccbababbaabbcbccbbccabacbacbbaaaacaccabbbbcbabc...

output:


result: