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