CSES - Optimointi

Oletko tehnyt brute force -koodin, jossa lasketaan bittien määriä (esim. __builtin_popcount), mutta koodi on liian hidas?

Ei hätää, koska voit nopeuttaa koodia lisäämällä alkuun seuraavan:

#pragma GCC target ("arch=sandybridge")

Tässä arch-arvona on "sandybridge", joka toimii esim. CSES:ssä. Voit tarkastaa tällä komennolla, mikä on oman koneesi arch-arvo:

g++ -march=native -Q --help=target

Entä jos haluat nopeuttaa koodia lisää? Yksi toimiva kikka on muuttaa silmukoita niin, että yhden kierroksen aikana tehdään monta askelta.

Tarkastellaan esimerkkinä seuraavaa koodia, joka laskee kertoman N!N! modulo MM:

ll k = 1;
for (int i = 1; i <= N; i++) {
    k = k*i%M;
}

Kun N=109N=10^9, koodi vie aikaa 6 sekuntia. Voimme kuitenkin muuttaa koodia näin:

ll k1 = 1, k2 = 1;
for (int i = 1; i <= N; i += 2) {
    k1 = k1*i%M;
    k2 = k2*(i+1)%M;
}
ll k = k1*k2%M;

Tämän muutoksen jälkeen aikaa kuluukin vain 3 sekuntia. Entä jos teemme silmukan sisällä vielä enemmän askelia?