Submission #898835

#	Time	Username	Problem	Language	Result	Execution time	Memory
898835		Alish	Cubeword (CEOI19_cubeword)	C++17	100 / 100	560 ms	19128 KiB

cubeword

#include<bits/stdc++.h>

#pragma GCC optimize("O3")
#pragma GCC target("sse4")

using namespace std;

typedef long long           ll;
typedef pair<int, int>      pii;
typedef pair<ll, ll>        pll;
typedef long double         ld;


#define endl                '\n'
#define pb                  push_back
#define all(x)              x.begin(), x.end()
#define F                   first
#define S                   second
#define fast_io             ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define debug(x)            cerr<<#x<<" "<<x<<endl;

ll mod = 998244353;

const int N = 1e6+23, S= 63;
ll ans=0;
ll num[S][S][S];
ll cnt[11][S][S];
set<string> st[11];
int n;

ll power(ll a, ll b){
    ll ans=1;
    a%=mod;
    while(b){
        if(b&1) ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}

int get(char c){
    if(c>='a' && c<='z'){
        int t=c-'a';
        return t;
    }
    if(c>='A' && c<='Z'){
        int t=c-'A';
        t+=26;
        return t;
    }
    int t=c-'0';
    t+=52;
    return t;
}

ll za(int a, int b, int c, int d){
    if(a==b && b==c && c==d) return 1;
    if(a!=b && b==c && c==d) return 4;
    if(a==b && b==c && c!=d) return 4;
    if(a==b && b!=c && c==d) return 6;
    if(a!=b && b!=c && c==d) return 12;
    if(a!=b && b==c && c!=d) return 12;
    if(a==b && b!=c && c!=d) return 12;
    if(a!=b && b!=c && c!=d) return 24;
}

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

    for (int i=3; i<=10; i++){
        for (string s : st[i]){
            char c=s.back();
            int t=get(c);
            c=s[0];
            int r=get(c);
            cnt[i][r][t]++;
        }
        for (int a=0; a<S; a++) for (int b=a; b<S; b++) for (int c=b; c<S; c++) num[a][b][c]=0;
        for (int a=0; a<S; a++) for (int b=a; b<S; b++) for (int c=b; c<S; c++) for (int x=0; x<S; x++)num[a][b][c]=(num[a][b][c]+cnt[i][x][a]*cnt[i][x][b]%mod*cnt[i][x][c]%mod)%mod;
        for (int a=0; a<S; a++) for (int b=a; b<S; b++) for (int c=b; c<S; c++) for (int d=c; d<S; d++) {
            ll temp = (num[a][b][c]*num[a][b][d]%mod*num[a][c][d]%mod*num[b][c][d]%mod)%mod;
            temp=temp*za(a, b, c, d)%mod;
            ans=(ans+temp)%mod;
        }
    }
    cout<<ans<<endl;

}

Compilation message (stderr)

cubeword.cpp: In function 'll za(int, int, int, int)':
cubeword.cpp:66:1: warning: control reaches end of non-void function [-Wreturn-type]
   66 | }
      | ^

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