| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1040817 |
2024-08-01T10:00:28 Z |
anton |
Cubeword (CEOI19_cubeword) |
C++17 |
|
256 ms |
21440 KB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int MOD = 998244353LL;
const int MAX_N =16LL;
int nbP[MAX_N][MAX_N];
int mid[MAX_N][MAX_N][MAX_N][MAX_N];
int RES = 0;
vector<pii> cube_edges = {
{0, 1},
{1, 2},
{2, 3},
{3, 0},
{4, 5},
{5, 6},
{6, 7},
{7, 4},
{0, 4},
{1, 5},
{2, 6},
{3, 7},
};
bool is_palindrome(string s){
bool ok = true;
for(int i = 0; i<(s.size()+1)/2; i++){
ok &= (s[i] == s[s.size()-i-1]);
}
return ok;
}
int mexp(int a, int b){
int res = 1;
vector<int>pows(1, a);
for(int i= 1; i<35; i++){
pows.push_back((pows.back()*pows.back())%MOD);
}
for(int i = 0; i<35; i++){
if(0LL!=((1LL<<i)&b)){
res = (res * pows[i])%MOD;
}
}
return res;
}
unordered_map<int, int> inv;
int modinv(int a){
if(inv.find(a)!=inv.end()){
return inv[a];
}
int b= mexp(a, MOD-2);
inv[a] = b;
assert((a*b)%MOD == 1);
return b;
}
vector<pair<int, vector<int>>> iterate_all(int nbSteps, int maxC){
vector<int> cur = vector<int>(nbSteps, 0);
vector<pair<int, vector<int>>> res;
bool ok = true;
for(int first_v = 0; first_v <maxC; first_v++){
cur =vector<int>(nbSteps, 0);
cur[0] = first_v;
ok =true;
while(ok){
cur.back()++;
for(int i = nbSteps-1; i>1; i--){
if(cur[i]>first_v){
cur[i-1]++;
cur[i] = 0;
}
}
if(cur[1] >first_v){
ok = false;
cur[1] = 0;
}
int nb_same = 0;
for(auto e: cur){
if(e == first_v){
nb_same++;
}
}
res.push_back({nbSteps * modinv(nb_same), cur});
}
}
return res;
}
vector<pair<int, vector<int>>> all(int len, int base){
vector<int> cur = vector<int>(len, 0);
vector<pair<int, vector<int>>> res;
bool ok = true;
while(ok){
cur.back()++;
for(int i = len-1; i>0; i--){
if(cur[i]>=base){
cur[i-1]++;
cur[i] = 0;
}
}
if(cur[0] >=base){
ok = false;
cur[0] = 0;
}
res.push_back({1, cur});
}
return res;
}
vector<pair<int, vector<int>>> all_weighted(int len, int base){
vector<int> cur = vector<int>(len, 0);
vector<pair<int, vector<int>>> res;
bool ok = true;
while(ok){
cur.back()++;
for(int i = len-1; i>0; i--){
if(cur[i]>=base){
cur[i-1]++;
cur[i] = 0;
}
}
if(cur[0] >=base){
ok = false;
cur[0] = 0;
}
res.push_back({1, cur});
}
for(pair<int, vector<int>>& e: res){
int oc= 1;
for(int i = 0; i<4; i++){
auto edge = cube_edges[i];
oc =(oc * nbP[e.second[edge.first]][e.second[edge.second]])%MOD;
}
e.first = oc;
}
return res;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin>>N;
vector<set<string>> words(11);
for(int i = 0; i<N; i++){
string s;
cin>>s;
if(is_palindrome(s)){
words[s.size()].insert(s);
}
else{
words[s.size()].insert(s);
reverse(s.begin(), s.end());
words[s.size()].insert(s);
}
}
//vector<pair<int, vector<int>>> colorings= iterate_all(8,6);
for(int len = 3; len<=10; len++){
if(words[len].size()>0){
fill(&nbP[0][0], &nbP[MAX_N][0], 0);
fill(&mid[0][0][0][0], &mid[MAX_N][0][0][0], 0);
for(auto e: words[len]){
int a= e[0]-'a';
int b= e.back()-'a';
nbP[a][b]++;
}
vector<pair<int, vector<int>>> colorings= all_weighted(4,MAX_N);
for(auto e: colorings){
if(e.first>0){
/*cout<<"starting from "<<endl;
for(auto c: e.second){
cout<<c<<" ";
}
cout<<endl;*/
int i= 0;
for(auto f: all(2, MAX_N)){
pii up = {f.second[0], f.second[1]};
//cout<<up.first<<" "<<up.second<<endl;
mid[up.first][up.second][e.second[2]][e.second[3]] = (mid[up.first][up.second][e.second[2]][e.second[3]] + ((nbP[e.second[0]][up.first]*nbP[e.second[1]][up.second])%MOD * e.first)%MOD)%MOD;
//cout<<up.first<<" "<<up.second<<" "<<e.second[2]<<" "<<e.second[3]<<" "<<mid[up.first][up.second][e.second[2]][e.second[3]]<<endl;
}
}
}
for(auto e: colorings){
auto v = e.second;
RES = (RES + (mid[v[0]][v[1]][v[2]][v[3]] * mid[v[3]][v[2]][v[1]][v[0]])%MOD);
}
}
}
cout<<RES<<endl;
}
Compilation message
cubeword.cpp: In function 'bool is_palindrome(std::string)':
cubeword.cpp:31:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for(int i = 0; i<(s.size()+1)/2; i++){
| ~^~~~~~~~~~~~~~~
cubeword.cpp: In function 'int main()':
cubeword.cpp:205:21: warning: unused variable 'i' [-Wunused-variable]
205 | int i= 0;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
256 ms |
21440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
256 ms |
21440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
256 ms |
21440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
256 ms |
21440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
