Submission #447259

#	Time	Username	Problem	Language	Result	Execution time	Memory
447259		yungyao	Cubeword (CEOI19_cubeword)	C++17	100 / 100	380 ms	19524 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 dp[maxn][maxn][maxn]{};
int perm_cnt(int a,int b,int c,int d){
    int bb = 24,bbb = 1,cc = 1;
    if (a == b) bbb *= ++cc;
    else {bb /= bbb; bbb = 1; cc = 1;}
    if (b == c) bbb *= ++cc;
    else {bb /= bbb; bbb = 1; cc = 1;}
    if (c == d) bbb *= ++cc;
    bb /= bbb;
    return bb;
}
 
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()){
        int mx = 0;
        LL cnt[maxn][maxn]{};
        memset(dp,0,sizeof(dp));
        for (string s:st[len]){
            ++cnt[ctoi(s[0])][ctoi(s.back())];
            mx = max(mx,ctoi(s[0]));
        }
        for (int i=0;i<=mx;++i) for (int j=i;j<=mx;++j) for (int k=j;k<=mx;++k) for (int l=0;l<=mx;++l){
            dp[i][j][k] += cnt[i][l] * cnt[j][l] % mod * cnt[k][l] % mod;
            dp[i][j][k] %= mod;
        }
        for (int i=0;i<=mx;++i) for (int j=i;j<=mx;++j) for (int k=j;k<=mx;++k) for (int l=k;l<=mx;++l){
            ans += dp[i][j][k] * dp[i][j][l] % mod * dp[i][k][l] % mod * dp[j][k][l] % mod * perm_cnt(i,j,k,l);
            ans %= mod;
        }
    }
 
    cout << ans;
 
    return 0;
}

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