Google Kickstart 2018, ошибка округления в тестовом примере

Question

Я пытаюсь решить проблему Scrambled Words в Google Kickstart 2018, Round A.

У меня проблемы с генерацией входной строки. Вот указания, которые они дали

Третья строка содержит две строчные английские буквы S ₁ и S ₂ и пять целых чисел N, A, B,C и D. S ₁ и S ₂ - первые два символа строки профессора S, N - длина S, а остальные четыре целых числа - это параметры, которые вы должны использоватьчтобы сгенерировать символы S следующим образом:

Сначала мы определяем ord (c) как десятичное значение символа c и char (n) как значение символа десятичного n. Например, ord ('a') = 97 и char (97) = 'a'. Вы можете обратиться к таблице ASCII для других преобразований.

Теперь определите x ₁ = ord (S ₁ ), x ₂ = ord(S * 2 * тысяча двадцать шесть ). Затем используйте повторение ниже, чтобы сгенерировать x _i для i = 3 до N:

• x _i = (A * x _i-1 + B * x _i-2 + C) по модулю D.

Определяем S _i = char (97 + (x *)1044 * i по модулю 26)), для всех i = 3 до N.

Используя эти указания для тестового ввода,

1
5
axpaj apxaj dnrbt pjxdn abd
a a 50 1 1 1 30

Строка, которой я являюсьгенерируется

aapaapaapaapaapaapaapaapaapaapaapaapaapaapaapaapaa

Но строка, которая должна быть сгенерирована, является

aapxjdnrbtvldptfzbbdbbzxtndrvjblnzjfpvhdhhpxjdnrbt

Вот мой код

    char S1, S2;
    long N, A, B, C, D;
    cin >> S1 >> S2 >> N >> A >> B >> C >> D;
    A %= D;
    B %= D;
    C %= D;

    vector<char> S;
    S.push_back(S1);
    S.push_back(S2);

    for (int i = 2; i < N; i++) {
      long xi1 = (long)S[i - 1];
      long xi2 = (long)S[i - 2];
      long xi = (A * xi1) % D;
      xi += ((B * xi2) % D);
      xi += C;
      xi %= D;
      xi %= 26;

      char Si = (char)(97 + xi);
      S.push_back(Si);
    }

Answer 1

В вашем коде вы предполагаете, что S_i == x_i, что неправильно. Формула повторения определяется с помощью x_i, а не S_i, рассмотрим код ниже

#include <iostream>

int main(){
    long N = 4;
    long A = 1;
    long B = 1;
    long C = 1;
    long D = 30;

    std::string s = "aa";
    int xi1 = 97;
    int xi2 = 97;
    for (int i = 2; i < N; i++) {
      std::cout<<(int)xi1<<" "<<xi2<< " vs si:"<<(int)s[i-1]<<" "<<(int)s[i-2]<<std::endl;
      int xi = (A*xi1 + B*xi2 + C)%D;
      char si = 97 + (xi%26);
      std::cout<<"xi: "<<xi<<" vs "<<(int)si<<std::endl;
      s += si;
      xi2 = xi1;
      xi1 = xi;
      std::cout<<s<<std::endl;
      std::cout<<"------------------------"<<std::endl;
    }
    return 0;
}

с выводом:

97 97 vs si:97 97
xi: 15 vs 112
aap
------------------------
15 97 vs si:112 97
xi: 23 vs 120
aapx
------------------------