Submission #1108552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108552		crafticat	Cubeword (CEOI19_cubeword)	C++17	0 / 100	102 ms	30648 KiB

cubeword

#include <bits/stdc++.h>

using namespace std;


using ll = long long;
template<typename T>
using V = vector<T>;
using vi = V<int>;
using vb = V<bool>;
using pi = pair<ll,ll>;

#define F0R(i,n) for (ll i = 0; i < n;i++)
#define FOR(i, j, n) for(ll i = j; i < n;i++)
#define ckmin(x,y) x = min(x,y)
#define f first
#define pb push_back
#define sor(a,b) min(a,b), max(a,b)
const pi emp = {0, 0};

constexpr int MOD = 998244353;
struct mint {
    ll v;

    mint() = default;

    mint(ll v) : v(v % MOD) {

    }
    void operator+=(mint other) {
        v += other.v;
        v %= MOD;
    }
    void operator*=(mint other) {
        v *= other.v;
        v %= MOD;
    }
};

V<V<int>> g;

bool next_combination(std::vector<int>& comb, int n) {

    int cary = 1;
    for (int i = 0; i < comb.size(); ++i) {
        comb[i] += cary;

        if (comb[i] >= n) {
            comb[i] -= n;
            cary = 1;
        } else
            cary = 0;
    }

    return !cary;
}

mint solve(set<string> &strs) {
    int constA = 'f' - 'a';
    V<V<ll>> amount(constA, V<ll>(constA));
    set<char> pos;

    for (auto x : strs) {
        int beg = x[0] - 'a', end = x[x.size() - 1] - 'a';
        amount[beg][end]++;

    }

    vi arr(8, 0);
    mint sum = 0;

    do {
        mint result = 1;

        bool skipy = true;
        for (int x = 0; x < 8;x++) {
            for (auto y : g[x]) {
                result *= amount[arr[x]][arr[y]];
            }
        }
        sum += result;

    } while (next_combination(arr, constA - 1));
    return sum;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    int n; cin >> n;
    V<set<string>> strs(11);
    g.resize(8);
    g[0] = {};
    g[1] = {0};
    g[2] = {1};
    g[3] = {0, 2};
    g[4] = {0};
    g[5] = {4,3};
    g[6] = {4, 1};
    g[7] = {6,5,2};

    F0R(i, n) {
        string s; cin >> s;
        strs[s.size()].insert(s);
        std::reverse(s.begin(), s.end());
        strs[s.size()].insert(s);
    }

    mint ans = 0;
    for (auto s : strs) {
        if (s.empty()) continue;
        ans += solve(s);
    }

    cout << ans.v << "\n";

    return 0;
}

Compilation message (stderr)

cubeword.cpp: In function 'bool next_combination(std::vector<int>&, int)':
cubeword.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i = 0; i < comb.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~
cubeword.cpp: In function 'mint solve(std::set<std::__cxx11::basic_string<char> >&)':
cubeword.cpp:75:14: warning: unused variable 'skipy' [-Wunused-variable]
   75 |         bool skipy = true;
      |              ^~~~~

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