Submission #1178095

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178095		ByeWorld	Cubeword (CEOI19_cubeword)	C++20	100 / 100	267 ms	17072 KiB

cubeword

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
// #define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 3e5+10;
const int MAXA = 1e7+10;
const int INF = 1e9+10;
const int SQRT = 300;
const int LOG = 20;
const ld EPS = 1e-6;
const int MOD = 998244353;
int sum(int a, int b){ return (a+b)%MOD; }
void chsum(int &a, int b){ a = (a+b)%MOD; }
void chsub(int &a, int b){ a = (a+MOD-b)%MOD; }
int mul(int a, int b){ return (1ll*a*b)%MOD; }
void chmul(int &a, int b){ a = (1ll*a*b)%MOD; }
void chmn(int &a, int b){ a = min(a, b); }
void chmx(int &a, int b){ a = max(a, b); }
int expo(int a, int b){
    if(b==0) return 1;
    int te = expo(a, b/2); te = mul(te,te);
    return (b%2 ? mul(te,a) : te);
}

int n;
set <string> len[15];
int cnt[64][64];
int num[64][64][64];

int gan(char x){
    if('a'<=x && x<='z') return x-'a';
    if('A'<=x && x<='Z') return x-'A'+26;
    return x-'0'+52;
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    // cout << gan('T') << ' '<< gan('I') << " i\n";
    for(int i=1; i<=n; i++){
        string s; cin>>s;
        len[s.size()].insert(s);
        reverse(s.begin(), s.end());
        len[(int)s.length()].insert(s);
    }
    int ans = 0;
    int val = 64;
    for(int l=3; l<=10; l++){
        for(int pp=0; pp<val; pp++){
            for(int qq=0; qq<val; qq++){
                cnt[pp][qq] = 0;
                for(int kk=0; kk<val; kk++)
                    num[pp][qq][kk] = 0;
            }
        }
        for(auto xx : len[l]){
            cnt[gan(xx[0])][gan(xx.back())]++;
            // cout << gan(xx[0]) << ' ' << 
            // gan(xx.back()) << ' '<< cnt[gan(xx[0])][gan(xx.back())] << " pp\n";
        }
        for(int a=0; a<val; a++){
            for(int b=a; b<val; b++){
                for(int c=b; c<val; c++){
                    for(int d=0; d<val; d++){
                        chsum(num[a][b][c], mul(cnt[a][d], 
                            mul(cnt[b][d], cnt[c][d])));
                        // if(num[a][b][c] != 0){
                        //     cout << a <<' '<<b<<' '<<c<<' '<<
                        //     num[a][b][c]<<" abc\n";
                        // }
                    }
                }
            }
        }
        for(int a=0; a<val; a++){
            for(int b=a; b<val; b++){
                for(int c=b; c<val; c++){
                    for(int d=c; d<val; d++){
                        int te = mul(mul(num[a][b][c], num[a][b][d]), 
                            mul(num[a][c][d], num[b][c][d]));

                        int cons = 24;
                        if(a==b){
                            if(b==c){
                                if(c==d) cons = 1;
                                else cons = 4;
                            } else {
                                if(c==d) cons = 6;
                                else cons = 12;
                            }
                        } else {
                            if(b==c){
                                if(c==d) cons = 4;
                                else cons = 12;
                            } else {
                                if(c==d) cons = 12;
                                else cons = 24;
                            }
                        }

                        chsum(ans, mul(cons, te));
                    }
                }
            }
        }
    }
    cout << ans << '\n';
}

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