oj.uz

Submission #1097394

# Submission time Handle Problem Language Result Execution time Memory
1097394 2024-10-07T07:49:31 Z 0pt1mus23 Trener (COCI20_trener) C++14
22 / 110
 6 ms 1020 KB 
#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 = 23157982937,mod2=3615727, mod3=1e9+7,
            sze = 2e3,    
            inf = 1e9,    
            L = 30 ;

mt19937 rng(time(0));
int MOD,prim;
int dp[55][sze];
int pw[sze];
int pw2[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;
}


pair<int,pair<int,int>> hashle2(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 * pw2[i-1] % mod + mod)%mod;
        }
        if(i<n-1){
            pref = (pref + (s[i]-'a' +1) * 1LL * pw2[i] % mod + mod)%mod ;
        }
        h1 = (h1 + (s[i]-'a' +1) * 1LL * pw2[i] %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 ,
    pair<int,pair<int,int>> a2, pair<int,pair<int,int>> b2
    ){
    // cout<<a.second.first<<" , "<<a.second.second<<" "<<b.first<<endl;
    return ((a.second.first == b.first && a2.second.first == b2.first )|| ( a.second.second == b.first && a2.second.second == b2.first) );
}

void _0x0(){
    MOD = rng();
    prim = rng();
    pw[0]=1;
    pw2[0]=1;
    for(int i=1;i<sze;i++){
        pw[i]=(pw[i-1] * 1LL * prim + MOD )%MOD;
        pw2[i]=(pw2[i-1] * 1LL * mod2 + mod )%mod;
    }
    int n,k;
    cin>>n>>k;
    vector< vector< pair< pair<int,pair<int,int>>, pair<int,pair<int,int>>> > > lst(n+10);
    // 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);
            auto h2 = hashle2(s,i);
            // cout<<s<<" => "<<h.first<<" , "<<h.second.first<<" , "<<h.second.second<<endl;
            lst[i].pb({h,h2});
        }
    }
    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].first, lst[i-1][p].first, lst[i][j].second, lst[i-1][p].second)){
                    // cout<<i<<" => "<<j<<endl;
                    dp[i][j] = (dp[i][j] + dp[i-1][p] )%mod3 ;
                }
            }
        }
    }
    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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 860 KB Output is correct
2 Correct 5 ms 988 KB Output is correct
3 Correct 4 ms 860 KB Output is correct
4 Incorrect 6 ms 1020 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 860 KB Output is correct
6 Correct 5 ms 988 KB Output is correct
7 Correct 4 ms 860 KB Output is correct
8 Incorrect 6 ms 1020 KB Output isn't correct
9 Halted 0 ms 0 KB -