c++ - Google Kickstart 2018，测试用例中的圆形错误

Question

我正在尝试解决 Scrambled Words Google Kickstart 2018 A 轮问题。

我在生成输入字符串时遇到问题。这是他们给出的指示

The third line contains two lowercase English letters S₁ and S₂, and five integers N, A, B, C and D. S₁ and S₂ are the first two characters of the professor's string S, N is the length of S, and the other four integers are parameters that you should use to generate the characters of S, as follows:

First we define ord(c) as the decimal value of a character c and char(n) as the character value of a decimal n. For example, ord('a') = 97 and char(97) = 'a'. You can refer to ASCII table for other conversions.

Now, define x₁ = ord(S₁), x₂ = ord(S₂). Then, use the recurrence below to generate x_i for i = 3 to N:

• x_i = ( A * x_i-1 + B * x_i-2 + C ) modulo D.

We define S_i = char(97 + ( x_i modulo 26 )), for all i = 3 to 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
------------------------