Words, just words

sto provando a risolvere words2 e non ho capito in che punti dovrei esattamente applicare il modulo di 1000000007, comunque io ho provato aa metterlo a caso e ho fatto 20/100, qualcuno saprebbe dirmi cosa ho fatto di sbagliato?

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#pragma GCC optimize("Ofast")

using namespace std;

int main(){
    
string abc = ("abcdefghijklmnopqrstuvwxyz");
string word;cin>>word;
long long pos=0;
long long count=0;


long long res=1;
for(int i=0; i<word.length(); i++){
    int j=word.length()-1-i;
    pos = abc.find(word[i])+1;
    res=1;
    while(j>0){
        res = res*26;
        res = res %1000000007;
        //cout<<res<<" "<<j<<endl;
        j--;
    }
    count+=(pos*res)%1000000007;
}

cout<<(count%1000000007)-1;



}

Ciao, con count += pos * res % mod stai aggiungendo a count N volte un numero grande fino a \text{mod}-1. Il modo corretto per farlo sarebbe count = (count + pos * res) % mod. Tuttavia in questo caso N \cdot \text{mod} sta in un long long, quindi il problema è un altro.
In ognuna delle N iterazioni sui caratteri, calcoli la rispettiva potenza di 26 in \mathcal{O}(N), che porta la complessità del tuo codice a \mathcal{O}(N^2), troppo per entrare nel time limit con N \leq 100\ 000. Se inizi a calcolare le potenze dall’ultimo carattere della stringa, per passare dalla posizione i alla posizione i-1 fai \mathcal{O}(1) operazioni e di conseguenza la complessità scende a \mathcal{O}(N).

Un’altra osservazione che semplifica il codice: ricordando che ogni carattere corrisponde a un intero secondo il codice ASCII, abc.find(word[i])+1 è equivalente a word[i]-'a'+1 in quanto le lettere dalla a alla z sono mappate a interi consecutivi.

Questo è il tuo codice che con qualche modifica prende 100

#include <iostream>
using namespace std;

const int mod = 1000000007;

int main() {
  string word; cin >> word;
  long long count=0;
  long long res=1;
  for(int i = word.size()-1; i >= 0; --i) {
    long long pos = word[i] - 'a' + 1;
    if (i != int(word.size() - 1)) {
      res = res * 26 % mod;
    }
    count = (count + pos * res) % mod;
  }
  cout << (count + mod - 1) % mod << "\n";
}

grazie mille, non sai quanti dubbi mi hai risolto

1 Mi Piace

Mi accodo alla richiesta per lo stesso esercizio che sto risolvendo utilizzando Python,
non riesco a scendere sotto 1.1 secondi nei test 15,25 e 26.
Cosa mi sfugge?

with open('input.txt') as f:
    lines = f.readlines()
    lettere = reversed(lines[0].strip())
peso = 1
numero = -1
for lettera in lettere :
    numero = numero  + (ord(lettera) - 96) * peso
    peso = peso * 26
numero = numero % 1000000007
out_file = open("output.txt", "w")
out_file.write(str(numero))
out_file.close()

Ho cambiato linguaggio, e… in C++ rientro tranquillamente nei tempi, e prendo 100, con lo stesso identico algoritmo…

trovato il problema in Python, per alleggerire il calcolo del peso, devo fare il modulo.

peso = (peso * 26) % 1000000007