제출 #260474

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
260474		stefantaga	Cubeword (CEOI19_cubeword)	C++14	100 / 100	818 ms	19044 KiB

cubeword

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

// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()

// input
template<class T> void IN(T& x) {cin >> x;}
template<class H, class... T> void IN(H& h, T&... t) {IN(h); IN(t...); }

// output
template<class T1, class T2> void OUT(const pair<T1,T2>& x);
template<class T> void OUT(const T& x) {cout << x;}
template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); }
template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi," ",x.se);}
template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); }

//===================//
//  Added libraries  //
//===================//

// mod library
ll MOD=998244353;

inline ll mod(ll x_) {
    return (x_)%MOD;
}
ll modpow(ll x_, ll N_) {
    if(N_ == 0) return 1;
    ll a = modpow(x_,N_/2);
    a = (a*a)%MOD;
    if(N_%2) a = (a*x_)%MOD;
    return a;
}
ll inv(ll x_) {
    return modpow(x_, MOD-2);
}
class mi {
public:
    mi(ll v=0) {value = v;}
    mi  operator+ (ll rs) {return value+rs;}
    mi  operator- (ll rs) {return value-rs+MOD;}
    mi  operator* (ll rs) {return mod(value*rs);}
    mi  operator/ (ll rs) {return mod(value*inv(rs));}
    mi& operator+=(ll rs) {*this = (*this)+rs; return *this;}
    mi& operator-=(ll rs) {*this = (*this)-rs; return *this;}
    mi& operator*=(ll rs) {*this = (*this)*rs; return *this;}
    mi& operator/=(ll rs) {*this = (*this)/rs; return *this;}
    operator ll&() {return value;}

    ll value;
};
typedef vector<mi> vmi;

//===================//
//end added libraries//
//===================//

void program();
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    program();
}


//===================//
//   begin program   //
//===================//

const int MX = 62;
int n;
string s;
set<string> S;
mi cnt[11][MX][MX];
mi ways[MX][MX][MX];

void modify(char& c) {
    if(c >= 'a' && c <= 'z') {
        c = c-'a';
    } else if(c >= 'A' && c <= 'Z') {
        c = c-'A'+26;
    } else {
        c = c-'0'+52;
    }
}
void addS() {
    if(S.count(s)) return;
    S.insert(s);
    cnt[s.sz][s[0]][s.back()] += 1ll;
}

void program() {
    IN(n);
    RE(i,11) RE(j,MX) RE(k,MX) cnt[i][j][k] = 0;
    RE(i,n) {
        IN(s);
        FOR(c,s) modify(c);
        addS();
        reverse(all(s));
        addS();
    }

    int fact[5], f[5];
    fact[0] = 1;
    RE(i,4) fact[i+1]=fact[i]*(i+1);

    mi ans;
    REP(l,3,11) {
        RE(i,MX) REP(j,i,MX) REP(k,j,MX) ways[i][j][k] = 0;

        RE(i,MX) REP(j,i,MX) REP(k,j,MX) RE(m,MX) ways[i][j][k] += cnt[l][i][m]*cnt[l][j][m]*cnt[l][k][m];
        RE(i,MX) REP(j,i,MX) REP(k,j,MX) ways[i][j][k] %= MOD;
        RE(i,MX) REP(j,i,MX) REP(k,j,MX) REP(m,k,MX) {
            mi added = ways[i][j][k]*ways[i][j][m]*ways[i][k][m]*ways[j][k][m];
            f[0]=i, f[1]=j, f[2]=k, f[3]=m;
            char ways=24, cnt=1;
            REP(i,1,4) {
                if(f[i]!=f[i-1]) {
                    ways/=fact[cnt];
                    cnt=0;
                }
                cnt++;
            }
            ways/=fact[cnt];
            ans += added*ll(ways);
        }
    }
    ans %= MOD;
    OUTL((ll)ans);
}

컴파일 시 표준 에러 (stderr) 메시지

cubeword.cpp: In function 'void addS()':
cubeword.cpp:114:19: warning: array subscript has type 'char' [-Wchar-subscripts]
     cnt[s.sz][s[0]][s.back()] += 1ll;
                   ^
cubeword.cpp:114:29: warning: array subscript has type 'char' [-Wchar-subscripts]
     cnt[s.sz][s[0]][s.back()] += 1ll;
                             ^
cubeword.cpp: In function 'void program()':
cubeword.cpp:144:35: warning: array subscript has type 'char' [-Wchar-subscripts]
                     ways/=fact[cnt];
                                   ^
cubeword.cpp:149:27: warning: array subscript has type 'char' [-Wchar-subscripts]
             ways/=fact[cnt];
                           ^

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