oj.uz

Submission #885201

# Submission time Handle Problem Language Result Execution time Memory
885201 2023-12-09T08:49:52 Z vjudge1 Trener (COCI20_trener) C++17
0 / 110
 4 ms 1032 KB 
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define endl '\n'
using namespace std;
const int MOD = 1e9 + 7;
const int p = 31;

int n,k,inv;
vector<int> pw;

int fpow(int a, int b){
    
    int ans=1;
    while(b){
        if(b&1) ans=(ans*a)%MOD;
        a=(a*a)%MOD;
        b>>=1;
    }
    return ans;
}

int calc(string const& s){
    
    int val=0;
    for(int i=0;i<s.size();i++){
        val= (val + (s[i]-'a'+1)*pw[i])%MOD;
    }
    
    return val;
}

void solve(){
    cin>>n>>k;
    
    map<int,int> dp;
    //i=1
    for(int j=0;j<k;j++){
        string s; cin>>s;
        int hash=calc(s);
        dp[hash]=1;
    }
    
    int i;
    for(i=2;i<=n-1;i++){
        for(int j=0;j<k;j++){
            string s; cin>>s;
            int hash=calc(s);
            
            int h1=hash;
            int ex=s[i-1]-'a' + 1; ex=(ex * pw[i-1])%MOD;
            h1=h1-ex;  h1%=MOD;
            
            int h2=hash; ex=s[0]-'a' + 1; 
            h2=h2-ex; h2%=MOD;
            h2= (h2*inv)%MOD;
            
            if(h1!=h2)
                dp[hash]= (dp[h1] + dp[h2])%MOD;
            else
                dp[hash]= dp[h1];
        }
    }
    
    //i=n
    int ans=0;
    for(int j=0;j<k;j++){
        string s; cin>>s;
        int hash=calc(s);
        int h1=hash;
        int ex=s[n-1]-'a' + 1; ex=(ex * pw[n-1])%MOD;
        h1=h1-ex;  h1%=MOD;
            
        int h2=hash; ex=s[0]-'a' + 1; 
        h2=h2-ex; h2%=MOD;
        h2= (h2*inv)%MOD;
        
        if(h1!=h2)
            dp[hash]= (dp[h1] + dp[h2])%MOD;
        else
            dp[hash]= dp[h1];
        
        ans=(ans+dp[hash])%MOD;
    }
    cout<<ans<<endl;
}

int32_t main(){
    cin.tie(0)->sync_with_stdio(false);
    
    pw.pb(1);
    for(int i=1;i<=55;i++){
        pw.pb(p*pw[i-1]);
        pw[i]%=MOD;
    }
    inv=fpow(p,MOD-2);
    
    solve();
    return 0;
}

Compilation message

trener.cpp: In function 'long long int calc(const string&)':
trener.cpp:26:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 456 KB Output isn't correct
3 Halted 0 ms 0 KB -