25720번 - Longest Common Subsequence 다국어

Given a sequence $s$ of length $n$ and a sequence $t$ of length $m$, find the length of the longest common subsequence of $s$ and $t$.

There are multiple test cases. The first line of input contains an integer $T$ ($1\le T\le 10^3$), the number of test cases.

For each test case:

The only line contains seven integers: $n$, $m$, $p$, $x$, $a$, $b$, and $c$ ($1 \le n, m \le 10^6$, $0 \le x, a, b, c < p\le 10^9$). Here, $n$ is the length of $s$, and $m$ is the length of $t$.

To avoid large input, you should generate the sequences as follows:

For each $i = 1, 2, \ldots, n$ in order, update $x$ to $(a x^2 + b x + c) \bmod p$, and then set $s_i$ to $x$. And then, for each $i = 1, 2, \ldots, m$ in order, update $x$ to $(a x^2 + b x + c) \bmod p$, and then set $t_i$ to $x$.

It is guaranteed that both the sum of $n$ and the sum of $m$ over all test cases do not exceed $10^6$.

For each test case:

Output a single line with a single integer: the length of the longest common subsequence of $s$ and $t$.

In the first sample, $s=[3,13,183,905]$ and $t=[731,565,303]$.

In the second sample, $s=[0,0,0]$ and $t=[0,0,0,0]$.