Submission #1041168

#TimeUsernameProblemLanguageResultExecution timeMemory
1041168antonCubeword (CEOI19_cubeword)C++17
100 / 100
258 ms18236 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> const int MOD = 998244353LL; const int MAX_N =62LL; int nbP[MAX_N][MAX_N]; int D[MAX_N][MAX_N][MAX_N]; int RES = 0; bool is_palindrome(string s){ bool ok = true; for(int i = 0; i<(s.size()+1)/2; i++){ ok &= (s[i] == s[s.size()-i-1]); } return ok; } int mexp(int a, int b){ int res = 1; vector<int>pows(1, a); for(int i= 1; i<35; i++){ pows.push_back((pows.back()*pows.back())%MOD); } for(int i = 0; i<35; i++){ if(0LL!=((1LL<<i)&b)){ res = (res * pows[i])%MOD; } } return res; } unordered_map<int, int> inv; int modinv(int a){ if(inv.find(a)!=inv.end()){ return inv[a]; } int b= mexp(a, MOD-2); inv[a] = b; assert((a*b)%MOD == 1); return b; } map<char, int> assign; void construct_table(){ for(char c= 'a'; c<='z'; c++){ assign[c] = assign.size(); } for(char c= 'A'; c<='Z'; c++){ assign[c] = assign.size(); } for(char c= '0'; c<='9'; c++){ assign[c] = assign.size(); } } vector<int> transform(string s){ vector<int> res(s.size()); for(int i = 0; i<s.size(); i++){ res[i] = assign[s[i]]; } return res; } int fact(int u){ if(u == 0){ return 1; } return fact(u-1)*u; } int nbperm(vector<int>& v){ int res= 24; int streak =1; for(int i = 1; i<v.size(); i++){ if(v[i] == v[i-1]){ streak++; res/=streak; } else{ streak=1; } } return res; } int prod(vector<int> v){ int res= 1; for(auto e: v){ res= (res*e)%MOD; } return res; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int N; cin>>N; vector<unordered_set<string>> words(11); construct_table(); for(int i = 0; i<N; i++){ string s; cin>>s; if(is_palindrome(s)){ words[s.size()].insert(s); } else{ words[s.size()].insert(s); reverse(s.begin(), s.end()); words[s.size()].insert(s); } } //vector<pair<int, vector<int>>> colorings= iterate_all(8,6); for(int len = 3; len<=10; len++){ fill(&nbP[0][0], &nbP[MAX_N][0], 0); fill(&D[0][0][0], &D[MAX_N][0][0], 0); for(auto e: words[len]){ auto v = transform(e); int a= v[0]; int b= v.back(); nbP[a][b]++; } for(int i = 0; i<MAX_N; i++){ for(int j = i; j<MAX_N; j++){ for(int k = j; k<MAX_N; k++){ for(int l = 0; l<MAX_N; l++){ D[i][j][k] = (D[i][j][k]+((nbP[l][i]*nbP[l][j])%MOD*nbP[l][k])%MOD)%MOD; } } } } int cur= 0; int coef = 24; vector<int> cv; for(int i = 0; i<MAX_N; i++){ cv.push_back(i); for(int j = i; j<MAX_N; j++){ cv.push_back(j); for(int k = j; k<MAX_N; k++){ cv.push_back(k); for(int h = k; h<MAX_N; h++){ cv.push_back(h); int coef = nbperm(cv); coef = (coef*D[i][j][k])%MOD; coef = (coef*D[j][k][h])%MOD; coef = (coef*D[i][k][h])%MOD; coef = (coef*D[i][j][h])%MOD; RES =(RES+coef)%MOD; cv.pop_back(); } cv.pop_back(); } cv.pop_back(); } cv.pop_back(); } } cout<<RES<<endl; }

Compilation message (stderr)

cubeword.cpp: In function 'bool is_palindrome(std::string)':
cubeword.cpp:16:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(int i = 0; i<(s.size()+1)/2; i++){
      |                    ~^~~~~~~~~~~~~~~
cubeword.cpp: In function 'std::vector<long long int> transform(std::string)':
cubeword.cpp:67:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int i = 0; i<s.size(); i++){
      |                    ~^~~~~~~~~
cubeword.cpp: In function 'long long int nbperm(std::vector<long long int>&)':
cubeword.cpp:84:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(int i = 1; i<v.size(); i++){
      |                    ~^~~~~~~~~
cubeword.cpp: In function 'int main()':
cubeword.cpp:147:13: warning: unused variable 'cur' [-Wunused-variable]
  147 |         int cur= 0;
      |             ^~~
cubeword.cpp:148:13: warning: unused variable 'coef' [-Wunused-variable]
  148 |         int coef = 24;
      |             ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...