제출 #1097392

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1097392		0pt1mus23	Trener (COCI20_trener)	C++14	22 / 110	4 ms	860 KiB

trener

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

#define int unsigned long long
#define ins insert      
#define pb push_back

#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
#define endl '\n'
#define _ << " " <<

const int mod = 998244353,       
            sze = 2e3,    
            inf = 1e9,    
            L = 30 ;

mt19937_64 rng(time(0));
int MOD,prim;
int dp[55][sze];
int pw[sze];

pair<int,pair<int,int>> hashle(string &s,int &n){
    pair<int,pair<int,int>> hash;
    int h1 = 0;
    int pref =0;
    int suff =0;
    for(int i=0;i<n;i++){
        if(i>0){
            suff = ((suff + (s[i]-'a' +1)*1LL * pw[i-1] % MOD + MOD)%MOD + MOD ) % MOD;
        }
        if(i<n-1){
            pref = ((pref + (s[i]-'a' +1) * 1LL * pw[i] % MOD + MOD)%MOD + MOD)%MOD ;
        }
        h1 = ((h1 + (s[i]-'a' +1) * 1LL * pw[i] %MOD + MOD) %MOD + MOD )% MOD;
        // cout<<s<< " "<< h1<<endl;
        // cout<<h1<<endl;
    }
    hash.first = h1;
    hash.second = {pref,suff};
    return hash;
}

int check(pair<int,pair<int,int>> a, pair<int,pair<int,int>> b){
    // cout<<a.second.first<<" , "<<a.second.second<<" "<<b.first<<endl;
    return (a.second.first == b.first || a.second.second == b.first);
}

void _0x0(){
    MOD = rng();
    prim = rng();
    pw[0]=1;
    for(int i=1;i<sze;i++){
        pw[i]=(pw[i-1] * 1LL * prim + MOD )%MOD;
    }
    int n,k;
    cin>>n>>k;
    vector< vector< pair<int,pair<int,int>>> > lst(n+10, vector< pair<int,pair<int,int>> >() );
    // string s="aaa";
    // int n = 3;
    // cout<<hashle(s,n).second.first <<" "<<hashle(s,n).second.second  <<endl;
    string s;
    for(int i=1;i<=n;i++){
        for(int j=0;j<k;j++){
            cin>>s;
            auto h = hashle(s,i);
            // cout<<s<<" => "<<h.first<<" , "<<h.second.first<<" , "<<h.second.second<<endl;
            lst[i].pb(h);
        }
    }
    for(int j=0;j<k;j++){
        dp[1][j]=1;
    }   
    // cout<<check(lst[2][0],lst[1][0])<<endl;

    for(int i=2;i<=n;i++){
        for(int j=0;j<k;j++){
            for(int p=0;p<k;p++){
                if(check(lst[i][j], lst[i-1][p])){
                    // cout<<i<<" => "<<j<<endl;
                    dp[i][j] += dp[i-1][p];
                }
            }
        }
    }
    int ans=0;
    for(int i=0;i<k;i++){
        ans+=dp[n][i];
    }
    putr(ans);
}
 
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt = 1;
    // cin>>tt;
    while(tt--){
        _0x0();
    }
 
    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 0 / 33
• Subtask 3: 0 / 55