QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#351669 | #8306. Boring Problem | Lynkcat | RE | 1ms | 5656kb | C++20 | 4.0kb | 2024-03-12 10:52:25 | 2024-03-12 10:52:27 |
Judging History
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...