Submission #1247621

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247621		abdelhakim	Cubeword (CEOI19_cubeword)	C++20	0 / 100	1194 ms	20872 KiB

cubeword

#include <bits/stdc++.h>
#define ll long long
#define inf (ll)(1e15) 
#define mod (ll)998244353
#define dbg(x) cerr <<#x << ' ' << x <<endl;
using namespace std;

void printvec(vector<ll>& v)
{
  for (auto &&i : v)
  {
    cout <<i<<' ';
  }
  cout << endl;
}
int mp[6][6];
vector<vector<ll>> adj(8);
ll anss(ll i, ll n, string cur, ll curans)
{
  if(i==8)
  {
    return curans;
  }
  ll sm=0;
  for (char cr='a';cr<='f';cr++)
  {
    ll factor=curans;
    for (auto &&e : adj[i])
    {
      factor*=mp[cur[e]-'a'][cr-'a'];
      if(factor>1e14)factor%=mod;
    }
    
    sm+=anss(i+1,n,cur+cr,factor);
    if(sm>1e14)sm%=mod;
  }
  if(sm>1e14)sm%=mod;
  return sm;
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  ll n;
  cin>>n;
  vector<string> s(n);
  ll sz=0;
  for (int i=0;i<n;i++)
  {
    cin>>s[i];
    sz=max(sz,(ll)s[i].size());
  }
  vector<vector<string>> szs(11);
  map<string,bool> vis;
  for (int j=0;j<7;j+=2)
  {
    adj[j+1].push_back(j);
  }
  for (int j=0;j<2;j++)
  {
    adj[j+2].push_back(j);
  }
  for (int j=4;j<6;j++)
  {
    adj[j+2].push_back(j);
  }
  for (int j=0;j<4;j++)
  {
    adj[j+4].push_back(j);
  }
  for (int i=0;i<8;i++)
  {
    sort(adj[i].begin(),adj[i].end());
  }
  // vector<string> s2;
  for (int i=0;i<n;i++)
  {
    if(vis[s[i]])continue;
    string rev=s[i];
    reverse(rev.begin(),rev.end());
    vis[rev]=1;
    vis[s[i]]=1;
    szs[s[i].size()].push_back(s[i]);
  }
  ll ans=0;
  for (int i=3;i<=10;i++)
  {
    if(szs[i].empty())continue;
    for (int i=0;i<6;i++)
    {
      for (int j=0;j<6;j++) mp[i][j]=0;
    }
    for (auto &&e : szs[i])
    {
      string rev=e;
      reverse(rev.begin(),rev.end());
      mp[e[0]-'a'][e.back()-'a']++;
      if(rev!=e)mp[e.back()-'a'][e[0]-'a']++;
      ans+=anss(0,n,"",1);
      if(ans>1e14)ans%=mod;
    }
    if(ans>1e14)ans%=mod;
  }
  cout << ans%mod << endl;
}

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