Submission #201079

#	Time	Username	Problem	Language	Result	Execution time	Memory
201079		georgerapeanu	Cubeword (CEOI19_cubeword)	C++11	100 / 100	521 ms	8716 KiB

cubeword

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

const int MOD = 998244353;

int char_to_int(char c){
    if('a' <= c && c <= 'z'){
        return c - 'a'; 
    }
    else if('A' <= c && c <= 'Z'){
        return c - 'A' + 'z' - 'a' + 1;
    }
    else{
        return c - '0' + 'Z' - 'A' + 'z' - 'a' + 2;
    }
}

int n;
string s;
vector<string> stuff[15];


int words[62][62];
int cnt[62][62][62];

int fact[] = {1,1,2,6,24};

int get_cnt(vector<int> v){
    int lst = -1;
    int cnt = 0;
    int ans = fact[4];

    for(auto it:v){
        if(lst == it){
            cnt++;
        }
        else{
            ans /= fact[cnt];
            lst = it;
            cnt = 1;
        }
    }
    
    ans /= fact[cnt];

    return ans;
}

int solve(vector<string> &stuff){

    if(stuff.empty()){
        return 0;
    }

    sort(stuff.begin(),stuff.end());
    stuff.resize(unique(stuff.begin(),stuff.end()) - stuff.begin());

    memset(words,0,sizeof(words));

    for(int i = 0;i < 62;i++){
        for(int j = i;j < 62;j++){
            for(int k = j;k < 62;k++){
                cnt[i][j][k] = 0;
            }
        }
    }

    for(auto it:stuff){
        words[char_to_int(it[0])][char_to_int(it.back())]++;
    }

    for(int a = 0;a < 62;a++){
        for(int b = a;b < 62;b++){
            for(int c = b;c < 62;c++){
                for(int d = 0;d < 62;d++){
                    cnt[a][b][c] = (cnt[a][b][c] + 1LL * words[a][d] * words[b][d] * words[c][d]) % MOD;
                }
            }
        }
    }

    int ans = 0;

    for(int a = 0;a < 62;a++){
        for(int b = a;b < 62;b++){
            for(int c = b;c < 62;c++){
                for(int d = c;d < 62;d++){
                    int num = get_cnt({a,b,c,d});
                    ans = (ans + (num + 0LL) * ((1LL * cnt[a][b][c] * cnt[a][b][d] % MOD) * (1LL * cnt[a][c][d] * cnt[b][c][d] % MOD) % MOD)) % MOD;
                }
            }
        }
    }

    return ans;
}

int main(){

    cin >> n;

    for(int i = 1;i <= n;i++){
        cin >> s;
        stuff[s.size()].push_back(s);
        reverse(s.begin(),s.end());
        stuff[s.size()].push_back(s);
    }

    int ans = 0;

    for(int i = 3;i <= 10;i++){
        ans += solve(stuff[i]);
        if(ans >= MOD){
            ans -= MOD;
        }
    }

    cout << ans;

    return 0;
}

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