プログラミングコンテストの名称 \(T_x\) は \(\mathrm{lcm}(|S_1|, |S_2|, |S_3|, |S_4|)\) の周期で繰り返しています。よって、 \(1\) 周期に \(T_x\) が TTPC となる個数 \(C\) と \(((N-1) \mod C) +1\) 回目に \(T_x\) が TTPC となる \(x\) を求めることができると、この問題を解くことができます。以下では \(N = ((N - 1) \mod C) + 1\) とします。

ナイーブな解法としては \(1\) 周期の \(T_x\) を列挙するという方法があります。部分点の制約では \(|S_i| \leq 50\) であり \(\mathrm{lcm}(|S_1|, |S_2|, |S_3|, |S_4|) \le 50^{4}\) となるため全て列挙することができます。しかし、満点の制約では \(|S_i| \le 10^3\) であり \(\mathrm{lcm}(|S_1|, |S_2|, |S_3|, |S_4|) \le 10^{12}\) となるため間に合いません。

そこで、文字列 \(S_1\) と \(S_2\) で TT を作り、文字列 \(S_3\) と \(S_4\) で PC を作りその \(2\) つを合わせて TTPC を作ることを考えます。 \(M_1 = \mathrm{lcm}(|S_1|, |S_2|)\) \(M_2 = \mathrm{lcm}(|S_3|, |S_4|)\) とすると \(T_x\) の前半 \(2\) 文字、後半 \(2\) 文字の周期はそれぞれ \(M_1, M_2\) となります。 \(M_1, M_2 \le 10^6\) であるため \(T_x\) の前半 \(2\) 文字と後半 \(2\) 文字の \(1\) 周期は列挙することができます。

\(k_1 \lt M_1\) を \(k_1 + 1\) 年目に前半 \(2\) 文字が TT 、 \(k_2 \lt M_2\) を \(k_2 + 1\) 年目に後半 \(2\) 文字が PC となるような非負整数とします。 前半 \(2\) 文字が TT となる \(x\) は非負整数 \(t\) を用いて \(tM_1 + k_1 + 1\) と表せます。追加で後半 \(2\) 文字が PC になるには、 \(tM_1 + k_1 \equiv k_2 \pmod{M_2}\) が必要十分です。

ここで、固定された \(t\) に対して条件を満たす \(k_1, k_2\) の組の個数は

\[ tM_1 \equiv -k_1 + k_2 \pmod{M_2} \]

となる \(k_1, k_2\) の組の個数に等しいです。よって \(-k_1 + k_2 \equiv i \pmod{M_2}\) となる \(k_1, k_2\) の組の個数を \(i = 0, 1, \dots M_2 - 1\) について求めれば \(0 \le t \lt M_1\) における TTPC となる \(x\) の個数がわかり、 \(1\) 周期に TTPC となる個数 \(C\) を求めることができます。これは畳み込みを用いることで計算することができます。

\(t\) を \(0\) から調べていき、 TTPC となる回数が \(N\) を超えた \(t\) について \(tM_1, tM_1 + 1, \dots, tM_1 + M_1 - 1\) を全探索することで \(N\) 回目に TTPC となる \(x\) を求めることができます。

計算量は \(O(M_1 + M_2 \log (M_2))\) です。

実装例(C++)