Submission #1093472

#TimeUsernameProblemLanguageResultExecution timeMemory
1093472LemserCubeword (CEOI19_cubeword)C++14
100 / 100
884 ms36304 KiB
#include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma GCC target("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #pragma GCC target("popcnt") using namespace std; using ll = long long; using ull = unsigned long long; using lld = long double; using vi = vector<int>; using vll = vector<ll>; using ii = pair<int,int>; using pll = pair<ll, ll>; using vii = vector<ii>; using vpll = vector<pll>; #define endl '\n' #define all(x) x.begin(),x.end() #define lsb(x) x&(-x) #define gcd(a,b) __gcd(a,b) #define sz(x) (int)x.size() #define mp make_pair #define pb push_back #define fi first #define se second #define fls cout.flush() #define fore(i,l,r) for(auto i=l;i<r;i++) #define fo(i,n) fore(i,0,n) #define forex(i,r,l) for(auto i=r; i>=l;i--) #define ffo(i,n) forex(i,n-1,0) bool cmin(int &a, int b){if(b<a){a=b;return 1;}return 0;} bool cmax(int &a, int b){if(b>a){a=b;return 1;}return 0;} void valid(ll in){cout<<((in)?"YES\n":"NO\n");} ll lcm(ll a, ll b){return (a/gcd(a,b))*b;} ll gauss(ll n){return (n*(n+1))/2;} const int N = 1e5 + 7, LOG=20,mod=998244353; int n,X=0; ll cnt[11][64][64][64], cnt2[11][64][64]; string s[N]; map<char, int> let; void test_case(){ cin>>n; set<string> st; fo(i,n){ cin>>s[i]; int t=sz(s[i]); st.insert(s[i]); reverse(all(s[i])); st.insert(s[i]); } for(auto e:st)cnt2[sz(e)][let[e[0]]][let[e.back()]]++; fore(t, 3, 11){ fo(d,X){ fo(a,X){ if(cnt2[t][d][a]==0)continue; fo(b,X){ if(cnt2[t][b][d]==0)continue; fo(c,X){ if(cnt2[t][d][c]==0)continue; ll aa=cnt2[t][d][a]; aa=aa*cnt2[t][b][d]; aa=aa*cnt2[t][d][c]; cnt[t][a][b][c]=(cnt[t][a][b][c]+aa)%mod; } } } } } ll ans=0; fore(t, 3, 11){ fo(a,X){ fo(b,X){ fo(c,X){ fo(d,X){ if(min({cnt[t][a][b][c],cnt[t][d][a][b],cnt[t][d][c][b],cnt[t][a][d][c]})==0)continue; ll aa=cnt[t][a][b][c]; aa=aa*cnt[t][d][a][b]; if(aa>=mod)aa%=mod; ll aa2=cnt[t][d][c][b]; aa2=aa2*cnt[t][a][d][c]; if(aa2>=mod)aa2%=mod; ans=ans+(aa*aa2)%mod; if(ans>=mod)ans-=mod; } } } } } ans%=mod; cout<<ans<<endl; } int main(){cin.tie(0)->sync_with_stdio(0); for(char a='a';a<='z';a++)let[a]=X++; for(char a='A';a<='Z';a++)let[a]=X++; for(char a='0';a<='9';a++)let[a]=X++; int t=1; // cin >> t; while(t--)test_case(); }

Compilation message (stderr)

cubeword.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("O3")
      | 
cubeword.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("unroll-loops")
      | 
cubeword.cpp: In function 'void test_case()':
cubeword.cpp:50:13: warning: unused variable 't' [-Wunused-variable]
   50 |         int t=sz(s[i]);
      |             ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...