oj.uz

Submission #885369

# Submission time Handle Problem Language Result Execution time Memory
885369 2023-12-09T14:32:02 Z vjudge1 Trener (COCI20_trener) C++17
0 / 110
 5 ms 860 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
    //cout<<"ff: ";
    for(int j=0;j<k;j++){
        string s; cin>>s;
        int hash=calc(s);
        dp[hash]=1;
        //cout<<dp[hash]<<" ";//dp
        //cout<<hash<<" ";//sub
    }
    //cout<<endl;

    int i;
    for(i=2;i<=n-1;i++){
        for(int j=0;j<k;j++){
            string s; cin>>s;
            int hash=calc(s);
            //cout<<hash<<": ";
            set<int> subs;
            int h1,ex; h1=0;
            int h2=hash; ex=s[0]-'a' + 1; 
            h2=h2-ex; h2%=MOD;
            h2= (h2*inv)%MOD;
            
            //cout<<h2<<" ";//sub
            dp[hash]=dp[h2];
            subs.insert(h2);
            for(int r=1;r<i;r++){ //0,...,r-1 / r+1,...,i-1
                h1=(h1+ (s[r-1]-'a'+1)*pw[r-1])%MOD;
                h2=(h2- (s[r] - 'a'+1)*pw[0])%MOD;
                h2=(h2*inv)%MOD;
                int sub=(h1+h2)%MOD;
                if(subs.find(sub)!=subs.end()){
                    (dp[hash]+=dp[sub])%MOD;
                    subs.insert(sub);
                }
               // cout<<sub<<" ";//sub
            }
            //cout<<endl;//sub
           //  cout<<dp[hash]<<" ";//dp
        }
        //cout<<endl;//dp
    }
    
    //i=n
    int ans=0;
    for(int j=0;j<k;j++){
        string s; cin>>s;
        int hash=calc(s);
        //cout<<hash<<": ";
        set<int> subs;
        int h1,ex; h1=0;
        int h2=hash; ex=s[0]-'a' + 1; 
        h2=h2-ex; h2%=MOD;
        h2= (h2*inv)%MOD;
        //cout<<h2<<" ";//sub
        dp[hash]=dp[h2];
        
        subs.insert(h2);
        for(int r=1;r<i;r++){ //0,...,r-1 / r+1,...,i-1
            h1=(h1+ (s[r-1]-'a'+1)*pw[r-1])%MOD;
            h2=(h2- (s[r] - 'a'+1)*pw[0])%MOD;
            h2=(h2*inv)%MOD;
            int sub=(h1+h2)%MOD;
            if(subs.find(sub)!=subs.end()){
                (dp[hash]+=dp[sub])%MOD;
                subs.insert(sub);
            }
            //cout<<sub<<" ";//sub
        }
        //(ans+=dp[hash])%MOD;
        //cout<<endl;//sub
        //cout<<dp[hash]<<" ";//dp
    }
    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++){
      |                 ~^~~~~~~~~
trener.cpp: In function 'void solve()':
trener.cpp:69:40: warning: value computed is not used [-Wunused-value]
   69 |                     (dp[hash]+=dp[sub])%MOD;
      |                     ~~~~~~~~~~~~~~~~~~~^~~~
trener.cpp:101:36: warning: value computed is not used [-Wunused-value]
  101 |                 (dp[hash]+=dp[sub])%MOD;
      |                 ~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
0 / 22.0

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

Subtask #2
0 / 33.0

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

Subtask #3
0 / 55.0

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