Submission #376509

#TimeUsernameProblemLanguageResultExecution timeMemory
376509kostia244Cubeword (CEOI19_cubeword)C++17
0 / 100
649 ms17332 KiB
#pragma GCC optimize("unroll-loops") #pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2") #include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template<typename T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<ll> vll; #define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in) #define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in) #define REP(i,b) FOR(i,0,b,1) #define REPD(i,b) FORD(i,b,0,1) #define pb push_back #define mp make_pair #define ff first #define ss second #define all(x) begin(x), end(x) #define MANY_TESTS int tcase; cin >> tcase; while(tcase--) const double EPS = 1e-9; const int MOD = 1e9+7; const ll INFF = 1e18; const int INF = 1e9; const ld PI = acos((ld)-1); const vi dy = {1, 0, -1, 0, -1, 1, 1, -1}; const vi dx = {0, 1, 0, -1, -1, 1, -1, 1}; void DBG(){cout << "]" << endl;} template<typename T, typename ...U> void DBG(const T& head, const U... args){ cout << head << "; "; DBG(args...); } #define dbg(...) cout << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__); #define chk() cout << "Check at line(" << __LINE__ << ") hit." << endl; template<class T, unsigned int U> ostream& operator<<(ostream& out, const array<T, U> &v){out << "["; REP(i, U) out << v[i] << ", "; out << "]"; return out;} template <class T, class U> ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "[" << par.first << ";" << par.second << "]"; return out;} template <class T> ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; } template <class T, class U> ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; } template<class T> ostream& operator<<(ostream& out, const vector<T> &v){ out << "["; REP(i, v.size()) out << v[i] << ", "; out << "]"; return out;} template<class T> istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; } const int alpha = 52; const int mod = 998244353; uint D[11][alpha][alpha][alpha]; uint D_q[11][alpha][alpha][alpha]; uint cn[11][alpha][alpha]; uint cn_q[11][alpha][alpha]; inline __attribute__(( always_inline )) uint multiply(const uint &a, const uint &b, const uint &a_inv) { uint Q = (a_inv*1ll*b)>>32; return a*b - Q*mod; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); vector<int> cnv(150); REP(i, 26) cnv['a' + i] = i; REP(i, 26) { cnv['A' + i] = 26 + i; } REP(i, 10){ cnv['0' + i] = 52 + i; } int n; cin >> n; vector<string> strings(n); cin >> strings; REP(i, n){ string ns = strings[i]; reverse(all(ns)); strings.pb(ns); } sort(all(strings)); auto solve = [&](vector<string> &a){ int nn = a.size(); memset(D, 0, sizeof(D)); memset(cn, 0, sizeof(cn)); string xprev = ""; for(string x : a){ if(x == xprev) continue; int f = cnv[x[0]]; int s = cnv[x.back()]; cn[x.length()][f][s]++; xprev = x; } FOR(len, 3, 11, 1) REP(i, alpha) REP(j, alpha) { cn_q[len][i][j] = (uint64_t(cn[len][i][j])<<32)/mod; } FOR(len, 3, 11, 1){ REP(i, alpha){ REP(j, alpha){ REP(k, alpha){ REP(g, alpha){ uint res = multiply(cn[len][i][j], cn[len][i][k], cn_q[len][i][j]); res = multiply(cn[len][i][g], res, cn_q[len][i][g]); D[len][j][k][g] += res; if(D[len][j][k][g] >= 2*mod) D[len][j][k][g] -= 2*mod; } } } } } FOR(len, 3, 11, 1) REP(a, alpha) REP(b, alpha) REP(c, alpha){ D_q[len][a][b][c] = (uint64_t(D[len][a][b][c])<<32)/mod; } ll res = 0; FOR(len, 3, 11, 1){ REP(a, alpha){ REP(b, alpha){ REP(c, alpha){ REP(d, alpha){ uint x = multiply(D[len][a][d][c], D[len][a][d][b], D_q[len][a][d][c]); x = multiply(D[len][a][c][b], x, D_q[len][a][c][b]); x = multiply(D[len][d][c][b], x, D_q[len][d][c][b]); res += x; if(res >= 2*mod) res -= 2*mod; } } } } } res %= mod; return res; }; ll ans = solve(strings); cout << ans << "\n"; return 0; }

Compilation message (stderr)

cubeword.cpp: In lambda function:
cubeword.cpp:93:13: warning: unused variable 'nn' [-Wunused-variable]
   93 |         int nn = a.size();
      |             ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...