제출 #953602

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
953602		mircea_007	Cubeword (CEOI19_cubeword)	C++17	100 / 100	235 ms	17504 KiB

cubeword

#pragma GCC optimize("O3,unroll-loops")

#include <iostream>
#include <string>
#include <unordered_set>
#include <algorithm>

#define MOD 998244353
using ll = long long;

struct ZP {
  int x;
 
  ZP( int x = 0 ): x(x % MOD) {}
  ZP( ll x ): x(x % MOD) {}
  explicit operator int() { return x; }
 
  ZP operator *= ( const ZP& that ) { return *this = ZP( x * (ll)that.x ); }
  ZP operator += ( const ZP& that ) {
    x += that.x;
    if( x >= MOD )
      x -= MOD;
 
    return *this;
  }
 
  ZP operator * ( const ZP& that ) const { return ZP( *this ) *= that; }
  ZP operator + ( const ZP& that ) const { return ZP( *this ) += that; }
};


#define SIGMA 62
const int MINLEN = 3;
const int MAXLEN = 10;

int char_idx[128];

int freq[MAXLEN + 1][SIGMA][SIGMA];
ZP lfreq[SIGMA][SIGMA];
ZP triangle[SIGMA][SIGMA][SIGMA];

int main() {
  int n;
  std::cin >> n;

  // hash map
  std::unordered_set<std::string> words;

  for( int i = 0 ; i < n ; i++ ){
    std::string w;
    std::cin >> w;

    words.insert( w );

    std::reverse( w.begin(), w.end() );

    words.insert( w );
  }

  {
    int idx = 0;
    for( int ch = 'a' ; ch <= 'z' ; ch++ )
      char_idx[ch] = idx++;
    for( int ch = 'A' ; ch <= 'Z' ; ch++ )
      char_idx[ch] = idx++;
    for( int ch = '0' ; ch <= '9' ; ch++ )
      char_idx[ch] = idx++;
  }

  for( std::string w : words )
    freq[(int)w.size()][char_idx[(int)w.front()]][char_idx[(int)w.back()]]++;

  ZP ret = 0;
  for( int len = MINLEN ; len <= MAXLEN ; len++ ){
    for( int a = 0 ; a < SIGMA ; a++ )
      for( int b = 0 ; b < SIGMA ; b++ )
        lfreq[a][b] = freq[len][a][b];
    
    for( int a = 0 ; a < SIGMA ; a++ ){
      for( int b = a ; b < SIGMA ; b++ )
        for( int c = b ; c < SIGMA ; c++ ){
          triangle[a][b][c] = 0;
          
          for( int mij = 0 ; mij < SIGMA ; mij++ )
            triangle[a][b][c] += lfreq[a][mij] * lfreq[b][mij] * lfreq[c][mij];
        }
    }

    // fixam 4 colturi neadiacente (oricare doua unite printr-o diagonala de latura)
    for( int a = 0 ; a < SIGMA ; a++ ){
      int coefa = 24;
      int streaka = 1;

      for( int b = a ; b < SIGMA ; b++ ){
        int streakb = 1 + (b == a) * streaka;
        int coefb = coefa / streakb;
        
        for( int c = b ; c < SIGMA ; c++ ){
          int streakc = 1 + (c == b) * streakb;
          int coefc = coefb / streakc;
          
          for( int d = c ; d < SIGMA ; d++ ){
            int streakd = 1 + (d == c) * streakc;
            int coefd = coefc / streakd;

            ret += ZP(coefd) * triangle[a][b][c] * triangle[b][c][d] * triangle[a][c][d] * triangle[a][b][d];
          }
        }
      }
    }
  }

  printf( "%d\n", int(ret) );
  
  return 0;
}

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