제출 #1220301

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1220301		Trumling	Dynamic Diameter (CEOI19_diameter)	C++20	0 / 100	1 ms	576 KiB

diameter

//Trumling ©
//Αφόδευε υψηλά και ηγνάντει 
#include <bits/stdc++.h>
using namespace std; 

typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
#define INF 99999999999999999
#define MOD 998244353
#define all(x) x.begin(),x.end()
#define out(x) for(auto y:x)cout<<y;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);

ll n;
cin>>n;

vector<vector<vector<ll>>>arr(11,vector<vector<ll>>(26,vector<ll>(26,0)));
map<string,bool>se;
for(int i=0;i<n;i++)
    {
        string s;
        cin>>s;
        
        
        if(!se[s]);
        {
            arr[s.size()][s[0]-'a'][s[s.size()-1]-'a']++;
            se[s]=1;
        }
        for(int i=0;i<s.size()/2;i++)
            swap(s[i],s[s.size()-1-i]);

        if(!se[s]);
        {
            arr[s.size()][s[0]-'a'][s[s.size()-1]-'a']++; 
            se[s]=1; 
        }
    }

ll ans=0;
for(int c=3;c<=10;c++)
    for(int i=0;i<6;i++)
    {
        vector<ll>two(26,0);
        for(int j=0;j<26;j++)
        {
            two[j]+=arr[c][i][j];
            two[j]%=MOD;
        }
        
        vector<ll>three(26,0);
        for(int j=0;j<26;j++)
            for(int jj=0;jj<26;jj++)
            {
                three[j]+=(arr[c][jj][j]*two[jj])%MOD;
                three[j]%=MOD;
            }

        
        vector<ll>four(26,0);
        for(int j=0;j<26;j++)
            for(int jj=0;jj<26;jj++)
            {
                four[j]+=(arr[c][jj][j]*three[jj])%MOD;
                four[j]%=MOD;
            }

        
        for(int j=0;j<26;j++)
        {
            four[j]*=four[j];
            four[j]%=MOD;
        }

        ll ans1=0;
        for(int j=0;j<26;j++)
        {
            ans1+=(four[j]*arr[c][j][i])%MOD;
            ans1%=MOD;
        }
        
        vector<ll>back1(26,1);
        for(int j=0;j<26;j++)
            for(int jj=0;jj<26;jj++)
                if(two[jj])
                {
                    if(!back1[j])
                        back1[j]=1;

                    back1[j]*=arr[c][jj][j];
                    back1[j]%=MOD;
                }
                    
            
        for(int j=0;j<26;j++)
        {
            back1[j]*=back1[j];
            back1[j]%=MOD;
        }

        

        vector<ll>back2(26,0);
        for(int j=0;j<26;j++)
            for(int jj=0;jj<26;jj++)
            {
                back2[j]+=(back1[jj]*arr[c][jj][j])%MOD;
                back2[j]%=MOD;
            }
                

        
        vector<ll>back3(26,1);
        for(int j=0;j<26;j++)
            for(int jj=0;jj<26;jj++)
                if(three[jj])
                {
                    if(!back3[j])
                        back3[j]=1;
                    
                    back3[j]*=arr[c][jj][j];
                    back3[j]%=MOD;
                }
            
        for(int j=0;j<26;j++)
        {
            back3[j]*=back3[j];
            back3[j]%=MOD;
        }
             

        for(int j=0;j<26;j++)
        {
            back2[j]*=back3[j];
            back2[j]%=MOD;
        }
            
        //out(back3)
        //enter
        
        ll ans2=0;
        for(int j=0;j<26;j++)
        {
            ans2+=back2[j];
            ans2%=MOD;
        }
            
        
        ans+=(ans1*ans2)%MOD;
        ans%=MOD;
    }
cout<<ans;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 13
• Subtask 3: 0 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27