Submission #898849

#	Time	Username	Problem	Language	Result	Execution time	Memory
898849		Iliya_	Cubeword (CEOI19_cubeword)	C++14	84 / 100	1160 ms	8260 KiB

cubeword

//IN THE NAME OF GOD
#include<bits/stdc++.h>
#pragma GCC optimize("O2,unroll-loops")
#define endl        '\n'
#define F           first
#define S           second
#define pii         pair<int,int>
#define all(x)      x.begin(),x.end()
#define pb          push_back
#define fast_io     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define file_io     freopen("input.in" , "r" , stdin) ; freopen("output.out" , "w" , stdout);
using namespace std;
typedef long long ll; 
typedef long double dll;

const int N = 62, NN = 11, mod = 998244353; 
int hav[NN][N][N], havi[NN], can[NN][N], dp[N][N][N];
vector<string> vec[NN];

inline int f(char c){
     if (int(c) <= 57) return (int(c)-48);
     else if (int(c) <= 90) return (int(c)-65+10); 
     else return (int(c)-97+36);
}

inline char ff(int x){
     if (x < 10) return char(x+48);
     else if (x < 36) return char(x+65-10);
     else return char(x+97-36);
}

int32_t main(){
     fast_io;

     int n; cin >> n;
     string s, ss; int siz;  
     for(int i=1; i<=n; i++){
          cin >> s; ss = s;
          siz = s.size(); 
          havi[siz] = 1;
          vec[siz].pb(s); 
          reverse(all(ss));
          if (ss != s) vec[siz].pb(ss);   
     }
     for(int i=3; i<=10; i++){
          sort(all(vec[i]));
          for(int j=0; j<int(vec[i].size()); j++){
               if (j != 0 && vec[i][j] == vec[i][j-1]) continue;
               can[i][f(vec[i][j][0])] = 1;
               hav[i][f(vec[i][j][0])][f(vec[i][j].back())]++;
          }    
     }
     ll ans = 0, tmp;
     for(int i=3; i<=10; i++){
          if (!havi[i]) continue; 
          memset(dp,0,sizeof dp);
          for(int s1 = 0; s1<N; s1++){
               if (!can[i][s1]) continue; 
               for(int s2 = 0; s2<N; s2++){
                    if (!can[i][s2]) continue; 
                    for(int s3 = 0; s3 < N; s3++){
                         if (!can[i][s3]) continue; 
                         for(int put=0; put<N; put++) dp[s1][s2][s3] = (dp[s1][s2][s3]+1ll*hav[i][s1][put]*hav[i][s2][put]*hav[i][s3][put]%mod)%mod;
                    }
               }
          }
          for(int s1 = 0; s1<N; s1++){
               if (!can[i][s1]) continue; 
               for(int s2=0; s2<N; s2++){
                    if (!can[i][s2]) continue; 
                    for(int s3=0; s3<N; s3++){
                         if (!can[i][s3]) continue; 
                         for(int s4=0; s4<N; s4++){
                              if (!can[i][s4]) continue; 
                              tmp = 1ll*dp[s1][s2][s3]*dp[s1][s2][s4]%mod*dp[s1][s3][s4]%mod*dp[s2][s3][s4]%mod;
                              ans = (ans+tmp)%mod;
                         }
                    }
               }
          }
     }
     cout << ans << endl;

     return 0;
}

• Subtask 1: 21 / 21
• Subtask 2: 29 / 29
• Subtask 3: 34 / 34
• Subtask 4: 0 / 16