oj.uz

답안 #258006

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
258006 2020-08-05T08:02:18 Z MarcoMeijer Cubeword (CEOI19_cubeword) C++14
0 / 100
 1100 ms 132860 KB 
#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 ways1[MX][MX][MX];
mi ways2[MX][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;
}
mi ways(int i, int j, int k) {
    int f[3];
    f[0]=i; f[1]=j; f[2]=k;
    sort(f,f+3);
    return ways1[f[0]][f[1]][f[2]];
}

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();
    }

    mi ans;
    REP(l,3,11) {
        RE(i,MX) REP(j,i,MX) REP(k,j,MX) ways1[i][j][k] = 0;
        RE(i,MX) REP(j,i,MX) RE(k,MX) REP(m,k,MX) ways2[i][j][k][m] = 0;
        
        RE(i,MX) REP(j,i,MX) REP(k,j,MX) RE(m,MX) ways1[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) ways1[i][j][k] %= MOD;
        RE(i,MX) REP(j,i,MX) RE(k,MX) REP(m,k,MX) {
            ways2[i][j][k][m] = ways(k,i,j)*ways(m,i,j);
        }
        RE(i,MX) REP(j,i,MX) REP(k,i,MX) REP(m,(i==k?max(j,k):k),MX) {
            ll mult = (i==j?1ll:2ll)*(k==m?1ll:2ll);
            if(i!=k || j!=m) mult*=2;
            ans += ll(ways2[i][j][k][m]*ways2[k][m][i][j])*mult;
        }
    }
    ans %= MOD;
    OUTL((ll)ans);
}

Compilation message

cubeword.cpp: In function 'void addS()':
cubeword.cpp:115:19: warning: array subscript has type 'char' [-Wchar-subscripts]
     cnt[s.sz][s[0]][s.back()] += 1ll;
                   ^
cubeword.cpp:115:29: warning: array subscript has type 'char' [-Wchar-subscripts]
     cnt[s.sz][s[0]][s.back()] += 1ll;
                             ^

Subtask #1
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1155 ms 132860 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1155 ms 132860 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1155 ms 132860 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1155 ms 132860 KB Time limit exceeded
2 Halted 0 ms 0 KB -