제출 #446275

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
446275		benedict0724	Cubeword (CEOI19_cubeword)	C++17	21 / 100	608 ms	15768 KiB

cubeword

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll cnt[6][6][11];
ll ans = 0;
const ll mod = 998244353;
vector<int> k[8];
vector<int> V;
map<string, int> M;

void solve(int dep, int t, ll now)
{
    if(dep == 8)
    {
        ans = (ans + now)%mod;
        return;
    }
    else
    {
        for(int i=0;i<6;i++)
        {
            V.push_back(i);
            ll tmp = now;
            for(int j : k[dep])
            {
                tmp *= cnt[i][V[j]][t];
                tmp %= mod;
            }
            solve(dep+1, t, tmp);
            V.pop_back();
        }
    }
}

int main()
{
    int n; cin >> n;
    for(int i=1;i<=n;i++)
    {
        string s; cin >> s;

        string p = s;
        reverse(p.begin(), p.end());
        if(M[p]) continue;

        M[s] = 1;
        int t = s.size();
        int a = s[0] - 'a';
        int b = s[t-1] - 'a';
        bool flag = true;
        for(int i=0;i<t;i++)
        {
            if(s[i] != s[t-i-1]) flag = false;
        }

        if(a != b) { cnt[a][b][t]++; cnt[b][a][t]++; }
        else if(flag) cnt[a][a][t]++;
        else cnt[a][a][t] += 2;
    }

    k[1].push_back(0);
    k[2].push_back(0);
    k[3].push_back(1); k[3].push_back(2);
    k[4].push_back(0);
    k[5].push_back(1); k[5].push_back(4);
    k[6].push_back(2); k[6].push_back(4);
    k[7].push_back(3); k[7].push_back(5); k[7].push_back(6);

    for(int t=3;t<=10;t++)
    {
        solve(0, t, 1);
    }

    cout << ans;
}

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