QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#351668#8306. Boring ProblemLynkcatWA 4ms9380kbC++204.0kb2024-03-12 10:51:582024-03-12 10:51:59

Judging History

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

  • [2024-03-12 10:51:59]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:9380kb
  • [2024-03-12 10:51:58]
  • 提交

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;
		}

	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
...
*/

詳細信息

Test #1:

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

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: 5896kb

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: 5844kb

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: 0ms
memory: 5892kb

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: 0ms
memory: 3672kb

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
Wrong Answer
time: 4ms
memory: 9380kb

input:

1 4457 3
37 22 41
acbaccbbbccabccabbbbccaacabbabcbcccaabcccaaabcbaaaabbbcbcaccbbabcabbaabbcaaccbbbcbcbbacacbbaabacacbbabacababbbacacbacbccacbbcccaaccbabccbbccacbaccaccbcccbbcbacacbbcbacbacacbacbbcccccaababaccbabaccaaccbcacbccccbcbaccacccaacbbaccbcacbbaaccbababbaabbcbccbbccabacbacbbaaaacaccabbbbcbabc...

output:

257013897
706585420
452854947
672362232
987922813
739511163
602517401
434363937
306393647
119706745
249738694
69345318
475227945
872961127
86944484
899631239
340163908
696393489
42891565
981519207
937086138
316517672
925504704
144826839
42714511
733038446
855651186
130426515
71204267
665495836
21507...

result:

wrong answer 204th numbers differ - expected: '399261992', found: '399261993'