#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,isudgh=b;i<isudgh;i++)
#define SZ(x) ((int)(x).size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) {for(auto jhglkdfjg:v)cout<<jhglkdfjg<<" ";cout<<"\n";}
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef int ll;
typedef long long LL;
typedef pair<ll,ll> ii;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
const ll MOD=998244353,MAXA=62;
ll add(ll a, ll b){a+=b;if(a>=MOD)a-=MOD;return a;}
ll sub(ll a, ll b){a-=b;if(a<0)a+=MOD;return a;}
ll mul(LL a, LL b){return a*b%MOD;}
ll A; //alphabet
vector<vector<ll>> q,g={
{},
{0},
{0},
{0},
{1,2},
{1,3},
{2,3},
{4,5,6}
};
vector<ll>bor={0,0,0,1,0,1,2,4},tam={1,2,3,3,4,4,3,0};
vector<ll>pot(6);
vector<ll>dp[8];
ll get(ll i, ll j, ll h){
ll p=i-1-j;
ll ret=h/pot[p]%A;
// cout<<"get "<<i<<" "<<j<<" "<<h<<": "<<p<<": "<<ret<<"\n";
return ret;
}
ll go(ll i, ll h, ll c){
return (h*A+c)%pot[tam[i]];
}
vector<ii>vis;
inline ll f(ll i, ll h){
if(i==8)return 1;
ll &res=dp[i][h];
if(res!=-1)return res;
res=0;
vis.pb({i,h});
fore(c,0,A){// pongo c
ll resi=1;
for(auto j:g[i]){
ll d=get(i,j,h);
resi=mul(resi,q[c][d]);
}
// cout<<i<<""
if(resi)res=add(res,mul(resi,f(i+1,go(i,h,c))));
}
// cout<<i<<" "<<h<<": "<<res<<"\n";
return res;
}
ll solve(vector<string>&a){
if(!SZ(a))return 0;
// cout<<"solve "; imp(a);
ll n=SZ(a);
vector<char>c;
fore(i,0,n)c.pb(a[i][0]),c.pb(a[i].back());
sort(ALL(c));
vector<char> ci;
fore(i,0,SZ(c))if(!i||c[i]!=c[i-1])ci.pb(c[i]);
c=ci;
for(auto &s:a){
auto change=[&](char &j){
ll p=lower_bound(ALL(c),j)-c.begin();
j=p;
};
change(s[0]); change(s.back());
}
// imp(a);
A=SZ(c);
q=vector<vector<ll>>(A,vector<ll>(A));
set<string> st[A][A];
for(auto s:a){
st[int(s[0])][int(s.back())].insert(s);
reverse(ALL(s));
st[int(s[0])][int(s.back())].insert(s);
}
fore(i,0,A)fore(j,0,A)q[i][j]=SZ(st[i][j]);
/*fore(i,0,A){
imp(q[i]);
}*/
pot[0]=1;
fore(i,1,6)pot[i]=pot[i-1]*A;
ll res=f(0,0);
// cout<<"visited "<<SZ(vis)<<" states"<<endl;
for(auto [i,j]:vis)dp[i][j]=-1;
vis.clear();
return res;
}
const ll MAXV=11;
int main(){FIN;
ll n; cin>>n;
vector<string> b[MAXV];
fore(i,0,n){
string s;cin>>s;
b[SZ(s)].pb(s);
}
vector<ll>POT={1};
fore(i,0,5)POT.pb(POT.back()*MAXA);
fore(i,0,8){
dp[i]=vector<ll>(POT[(i?tam[i-1]:0)],-1);
// cout<<i<<": "<<SZ(dp[i])<<"\n";
}
// imp(POT); cout<<endl;
ll res=0;
fore(i,0,MAXV){
res=add(res,solve(b[i]));
}
// res=solve(b[5]);
cout<<res<<"\n";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
109 ms |
125936 KB |
Output is correct |
2 |
Correct |
103 ms |
125900 KB |
Output is correct |
3 |
Correct |
102 ms |
125984 KB |
Output is correct |
4 |
Correct |
98 ms |
125992 KB |
Output is correct |
5 |
Correct |
118 ms |
125952 KB |
Output is correct |
6 |
Correct |
106 ms |
125932 KB |
Output is correct |
7 |
Correct |
133 ms |
126068 KB |
Output is correct |
8 |
Correct |
124 ms |
126040 KB |
Output is correct |
9 |
Correct |
110 ms |
126128 KB |
Output is correct |
10 |
Correct |
104 ms |
126008 KB |
Output is correct |
11 |
Correct |
104 ms |
125944 KB |
Output is correct |
12 |
Correct |
114 ms |
126088 KB |
Output is correct |
13 |
Correct |
101 ms |
125948 KB |
Output is correct |
14 |
Correct |
105 ms |
125988 KB |
Output is correct |
15 |
Correct |
100 ms |
125992 KB |
Output is correct |
16 |
Correct |
102 ms |
126032 KB |
Output is correct |
17 |
Correct |
120 ms |
125988 KB |
Output is correct |
18 |
Correct |
99 ms |
125948 KB |
Output is correct |
19 |
Correct |
97 ms |
125916 KB |
Output is correct |
20 |
Correct |
109 ms |
125900 KB |
Output is correct |
21 |
Correct |
103 ms |
125972 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
109 ms |
125936 KB |
Output is correct |
2 |
Correct |
103 ms |
125900 KB |
Output is correct |
3 |
Correct |
102 ms |
125984 KB |
Output is correct |
4 |
Correct |
98 ms |
125992 KB |
Output is correct |
5 |
Correct |
118 ms |
125952 KB |
Output is correct |
6 |
Correct |
106 ms |
125932 KB |
Output is correct |
7 |
Correct |
133 ms |
126068 KB |
Output is correct |
8 |
Correct |
124 ms |
126040 KB |
Output is correct |
9 |
Correct |
110 ms |
126128 KB |
Output is correct |
10 |
Correct |
104 ms |
126008 KB |
Output is correct |
11 |
Correct |
104 ms |
125944 KB |
Output is correct |
12 |
Correct |
114 ms |
126088 KB |
Output is correct |
13 |
Correct |
101 ms |
125948 KB |
Output is correct |
14 |
Correct |
105 ms |
125988 KB |
Output is correct |
15 |
Correct |
100 ms |
125992 KB |
Output is correct |
16 |
Correct |
102 ms |
126032 KB |
Output is correct |
17 |
Correct |
120 ms |
125988 KB |
Output is correct |
18 |
Correct |
99 ms |
125948 KB |
Output is correct |
19 |
Correct |
97 ms |
125916 KB |
Output is correct |
20 |
Correct |
109 ms |
125900 KB |
Output is correct |
21 |
Correct |
103 ms |
125972 KB |
Output is correct |
22 |
Correct |
378 ms |
126028 KB |
Output is correct |
23 |
Correct |
422 ms |
126164 KB |
Output is correct |
24 |
Correct |
392 ms |
126160 KB |
Output is correct |
25 |
Correct |
386 ms |
126240 KB |
Output is correct |
26 |
Correct |
398 ms |
126236 KB |
Output is correct |
27 |
Correct |
363 ms |
126176 KB |
Output is correct |
28 |
Correct |
386 ms |
126052 KB |
Output is correct |
29 |
Correct |
376 ms |
126268 KB |
Output is correct |
30 |
Correct |
370 ms |
126056 KB |
Output is correct |
31 |
Correct |
349 ms |
126232 KB |
Output is correct |
32 |
Correct |
372 ms |
126476 KB |
Output is correct |
33 |
Correct |
367 ms |
126280 KB |
Output is correct |
34 |
Correct |
379 ms |
126224 KB |
Output is correct |
35 |
Correct |
372 ms |
126244 KB |
Output is correct |
36 |
Correct |
426 ms |
126040 KB |
Output is correct |
37 |
Correct |
463 ms |
126236 KB |
Output is correct |
38 |
Correct |
432 ms |
126120 KB |
Output is correct |
39 |
Correct |
452 ms |
126004 KB |
Output is correct |
40 |
Correct |
447 ms |
126044 KB |
Output is correct |
41 |
Correct |
419 ms |
126084 KB |
Output is correct |
42 |
Correct |
422 ms |
126184 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
109 ms |
125936 KB |
Output is correct |
2 |
Correct |
103 ms |
125900 KB |
Output is correct |
3 |
Correct |
102 ms |
125984 KB |
Output is correct |
4 |
Correct |
98 ms |
125992 KB |
Output is correct |
5 |
Correct |
118 ms |
125952 KB |
Output is correct |
6 |
Correct |
106 ms |
125932 KB |
Output is correct |
7 |
Correct |
133 ms |
126068 KB |
Output is correct |
8 |
Correct |
124 ms |
126040 KB |
Output is correct |
9 |
Correct |
110 ms |
126128 KB |
Output is correct |
10 |
Correct |
104 ms |
126008 KB |
Output is correct |
11 |
Correct |
104 ms |
125944 KB |
Output is correct |
12 |
Correct |
114 ms |
126088 KB |
Output is correct |
13 |
Correct |
101 ms |
125948 KB |
Output is correct |
14 |
Correct |
105 ms |
125988 KB |
Output is correct |
15 |
Correct |
100 ms |
125992 KB |
Output is correct |
16 |
Correct |
102 ms |
126032 KB |
Output is correct |
17 |
Correct |
120 ms |
125988 KB |
Output is correct |
18 |
Correct |
99 ms |
125948 KB |
Output is correct |
19 |
Correct |
97 ms |
125916 KB |
Output is correct |
20 |
Correct |
109 ms |
125900 KB |
Output is correct |
21 |
Correct |
103 ms |
125972 KB |
Output is correct |
22 |
Correct |
378 ms |
126028 KB |
Output is correct |
23 |
Correct |
422 ms |
126164 KB |
Output is correct |
24 |
Correct |
392 ms |
126160 KB |
Output is correct |
25 |
Correct |
386 ms |
126240 KB |
Output is correct |
26 |
Correct |
398 ms |
126236 KB |
Output is correct |
27 |
Correct |
363 ms |
126176 KB |
Output is correct |
28 |
Correct |
386 ms |
126052 KB |
Output is correct |
29 |
Correct |
376 ms |
126268 KB |
Output is correct |
30 |
Correct |
370 ms |
126056 KB |
Output is correct |
31 |
Correct |
349 ms |
126232 KB |
Output is correct |
32 |
Correct |
372 ms |
126476 KB |
Output is correct |
33 |
Correct |
367 ms |
126280 KB |
Output is correct |
34 |
Correct |
379 ms |
126224 KB |
Output is correct |
35 |
Correct |
372 ms |
126244 KB |
Output is correct |
36 |
Correct |
426 ms |
126040 KB |
Output is correct |
37 |
Correct |
463 ms |
126236 KB |
Output is correct |
38 |
Correct |
432 ms |
126120 KB |
Output is correct |
39 |
Correct |
452 ms |
126004 KB |
Output is correct |
40 |
Correct |
447 ms |
126044 KB |
Output is correct |
41 |
Correct |
419 ms |
126084 KB |
Output is correct |
42 |
Correct |
422 ms |
126184 KB |
Output is correct |
43 |
Execution timed out |
1143 ms |
157268 KB |
Time limit exceeded |
44 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
109 ms |
125936 KB |
Output is correct |
2 |
Correct |
103 ms |
125900 KB |
Output is correct |
3 |
Correct |
102 ms |
125984 KB |
Output is correct |
4 |
Correct |
98 ms |
125992 KB |
Output is correct |
5 |
Correct |
118 ms |
125952 KB |
Output is correct |
6 |
Correct |
106 ms |
125932 KB |
Output is correct |
7 |
Correct |
133 ms |
126068 KB |
Output is correct |
8 |
Correct |
124 ms |
126040 KB |
Output is correct |
9 |
Correct |
110 ms |
126128 KB |
Output is correct |
10 |
Correct |
104 ms |
126008 KB |
Output is correct |
11 |
Correct |
104 ms |
125944 KB |
Output is correct |
12 |
Correct |
114 ms |
126088 KB |
Output is correct |
13 |
Correct |
101 ms |
125948 KB |
Output is correct |
14 |
Correct |
105 ms |
125988 KB |
Output is correct |
15 |
Correct |
100 ms |
125992 KB |
Output is correct |
16 |
Correct |
102 ms |
126032 KB |
Output is correct |
17 |
Correct |
120 ms |
125988 KB |
Output is correct |
18 |
Correct |
99 ms |
125948 KB |
Output is correct |
19 |
Correct |
97 ms |
125916 KB |
Output is correct |
20 |
Correct |
109 ms |
125900 KB |
Output is correct |
21 |
Correct |
103 ms |
125972 KB |
Output is correct |
22 |
Correct |
378 ms |
126028 KB |
Output is correct |
23 |
Correct |
422 ms |
126164 KB |
Output is correct |
24 |
Correct |
392 ms |
126160 KB |
Output is correct |
25 |
Correct |
386 ms |
126240 KB |
Output is correct |
26 |
Correct |
398 ms |
126236 KB |
Output is correct |
27 |
Correct |
363 ms |
126176 KB |
Output is correct |
28 |
Correct |
386 ms |
126052 KB |
Output is correct |
29 |
Correct |
376 ms |
126268 KB |
Output is correct |
30 |
Correct |
370 ms |
126056 KB |
Output is correct |
31 |
Correct |
349 ms |
126232 KB |
Output is correct |
32 |
Correct |
372 ms |
126476 KB |
Output is correct |
33 |
Correct |
367 ms |
126280 KB |
Output is correct |
34 |
Correct |
379 ms |
126224 KB |
Output is correct |
35 |
Correct |
372 ms |
126244 KB |
Output is correct |
36 |
Correct |
426 ms |
126040 KB |
Output is correct |
37 |
Correct |
463 ms |
126236 KB |
Output is correct |
38 |
Correct |
432 ms |
126120 KB |
Output is correct |
39 |
Correct |
452 ms |
126004 KB |
Output is correct |
40 |
Correct |
447 ms |
126044 KB |
Output is correct |
41 |
Correct |
419 ms |
126084 KB |
Output is correct |
42 |
Correct |
422 ms |
126184 KB |
Output is correct |
43 |
Execution timed out |
1143 ms |
157268 KB |
Time limit exceeded |
44 |
Halted |
0 ms |
0 KB |
- |