Submission #447034

#	Time	Username	Problem	Language	Result	Execution time	Memory
447034		yungyao	Cubeword (CEOI19_cubeword)	C++17	50 / 100	1192 ms	16436 KiB

cubeword

using namespace std;
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <utility>
#include <memory.h>
#include <vector>
#include <bitset>

typedef pair<int,int> pii;
typedef long long LL;

#define iter(x) x.begin(),x.end()
#define F first
#define S second
#define pb push_back
#define mkp make_pair

#include <climits>
const int maxn = 70,mod = (119 << 23)^1;

int ctoi(char c){
    if (c >= 'a' and c <= 'p') return c - 'a';
    else if (c >= 'A' and c <= 'P') return c - 'A' + 16;
    else if (c > 'p' and c <= 'z') return c - 'p' + 31;
    else if (c > 'P' and c <= 'Z') return c - 'P' + 41;
    else return c - '0' + 52;
}

LL cnt[maxn][maxn];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    set <string> st[11];
    int n;

    cin >> n;
    for (int i=0;i<n;++i){
        string s; cin >> s;
        st[s.size()].insert(s);
        reverse(iter(s));
        st[s.size()].insert(s);
    }

    LL ans = 0;
    for (int len=3;len<=10;++len) if (!st[len].empty()){
        memset(cnt,0,sizeof(cnt));
        int mx = 0;
        for (string s:st[len]){
            ++cnt[ctoi(s[0])][ctoi(s.back())];
            mx = max(mx,max(ctoi(s[0]),ctoi(s.back())));
        }
        for (int i=0;i<=mx;++i) for (int j=0;j<=mx;++j) for (int k=0;k<=mx;++k) for (int l=0;l<=mx;++l){
            LL c[4]{};
            for (int p=0;p<=mx;++p){
                c[0] += (cnt[i][p] * cnt[j][p]) % mod * cnt[k][p];
                c[0] %= mod;
            }
            for (int p=0;p<=mx;++p){
                c[1] += (cnt[i][p] * cnt[j][p]) % mod * cnt[l][p];
                c[1] %= mod;
            }
            for (int p=0;p<=mx;++p){
                c[2] += (cnt[i][p] * cnt[k][p]) % mod * cnt[l][p];
                c[2] %= mod;
            }
            for (int p=0;p<=mx;++p){
                c[3] += (cnt[j][p] * cnt[k][p]) % mod * cnt[l][p];
                c[3] %= mod;
            }
            c[0] *= c[1]; c[0] %= mod;
            c[0] *= c[2]; c[0] %= mod;
            c[0] *= c[3]; c[0] %= mod;
            ans = (ans + c[0]) % mod;
        }
    }

    cout << ans;

    return 0;
}

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