QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#351666 | #8306. Boring Problem | Lynkcat | WA | 4ms | 9420kb | C++20 | 3.9kb | 2024-03-12 10:51:09 | 2024-03-12 10:51:11 |
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;
}
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
...
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3860kb
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: 3596kb
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: 3636kb
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: 5604kb
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: 5660kb
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: 9420kb
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'