제출 #1038339

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1038339		vjudge1	Cubeword (CEOI19_cubeword)	C++17	21 / 100	1148 ms	14288 KiB

cubeword

#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,isudgh=b;i<isudgh;i++)
#define SZ(x) ((int)(x).size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) {for(auto jhglkdfjg:v)cout<<jhglkdfjg<<" ";cout<<"\n";}
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MOD=998244353;

ll add(ll a, ll b){a+=b;if(a>=MOD)a-=MOD;return a;}
ll sub(ll a, ll b){a-=b;if(a<0)a+=MOD;return a;}
ll mul(ll a, ll b){return a*b%MOD;}

ll A; //alphabet
vector<vector<ll>> q,g={
	{},
	{0},
	{0},
	{0},
	{1,2},
	{1,3},
	{2,3},
	{4,5,6}
};
vector<ll>bor={0,0,0,1,0,1,2,4},tam={1,2,3,3,4,4,3,0};
vector<ll>pot(6);

unordered_map<ll,ll> dp[8];

ll get(ll i, ll j, ll h){
	ll p=i-1-j;
	ll ret=h/pot[p]%A;
	// cout<<"get "<<i<<" "<<j<<" "<<h<<": "<<p<<": "<<ret<<"\n";
	return ret;
}
ll go(ll i, ll h, ll c){
	return (h*A+c)%pot[tam[i]];
}
ll f(ll i, ll h){
	if(i==8)return 1;
	if(dp[i].count(h))return dp[i][h];
	ll &res=dp[i][h];
	fore(c,0,A){// pongo c
		ll resi=1;
		for(auto j:g[i]){
			ll d=get(i,j,h);
			resi=mul(resi,q[c][d]);
		}
		// cout<<i<<""
		if(resi)res=add(res,mul(resi,f(i+1,go(i,h,c))));
	}
	// cout<<i<<" "<<h<<": "<<res<<"\n";
	return res;
}
ll solve(vector<string>&a){
	// cout<<"solve "; imp(a);
	ll n=SZ(a);
	vector<char>c;
	fore(i,0,n)for(auto j:a[i])c.pb(j);
	sort(ALL(c));
	vector<char> ci;
	fore(i,0,SZ(c))if(!i||c[i]!=c[i-1])ci.pb(c[i]);
	c=ci;
	fore(i,0,n){
		for(auto &j:a[i]){
			ll p=lower_bound(ALL(c),j)-c.begin();
			j=p;
		}
	}
	// imp(a);
	A=SZ(c);
	q=vector<vector<ll>>(A,vector<ll>(A));
	set<string> st[A][A];
	for(auto s:a){
		st[s[0]][s.back()].insert(s);
		reverse(ALL(s));
		st[s[0]][s.back()].insert(s);
	}
	fore(i,0,A)fore(j,0,A)q[i][j]=SZ(st[i][j]);
	/*fore(i,0,A){
		imp(q[i]);
	}*/
	pot[0]=1;
	fore(i,1,6)pot[i]=pot[i-1]*A;
	fore(i,0,8)dp[i].clear();
	ll res=f(0,0);
	return res;
}
const ll MAXV=1e5+5;
int main(){FIN;
	ll n; cin>>n;
	vector<string> b[MAXV];
	fore(i,0,n){
		string s;cin>>s;
		b[SZ(s)].pb(s);
	}
	ll res=0;
	fore(i,0,MAXV){
		res=add(res,solve(b[i]));
	}
	// res=solve(b[5]);
	cout<<res<<"\n";
	return 0;
}

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

cubeword.cpp: In function 'll solve(std::vector<std::__cxx11::basic_string<char> >&)':
cubeword.cpp:81:10: warning: array subscript has type 'char' [-Wchar-subscripts]
   81 |   st[s[0]][s.back()].insert(s);
      |          ^
cubeword.cpp:81:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   81 |   st[s[0]][s.back()].insert(s);
      |            ~~~~~~^~
cubeword.cpp:83:10: warning: array subscript has type 'char' [-Wchar-subscripts]
   83 |   st[s[0]][s.back()].insert(s);
      |          ^
cubeword.cpp:83:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   83 |   st[s[0]][s.back()].insert(s);
      |            ~~~~~~^~

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