813B: The Golden Age

Need to take care of long long overflow. I use a log based solution to limit the max value for a and b. The official solution uses

while x <= L/ a
	x *= a;

and calculate the powers inside iteration

813D: Two Melodies(!!!)

Since we care only the last entry, we will keep track of dp[x][y] => last index of the each list

Obviously, we can enforce x > y due to symmetric rule,

The key is that to avoid intersecitons, we will update dp[x][y] only with dp[i][y], with i != y and i < x, because based on our dp definitely, we know that dp[i][y] gives no interseciton, and x has not been used by sequence ending at either i or y.

Conversely, if we update dp with dp[x][i], we can not guarantees that y has not been used by sequence ending at x yet.

Above proves that our scheme is sound. It is also complete because we cover all possible cases with a given y.

Another case to watch out for is the empty melody case, i.e., we need to decide when/where to start a new melody. To fix it, we change index from 0-based to 1-based, and mark dp[0][y] as the case with a single melody

then we start y from 0 to n, and then scan x from y + 1 to n need to know max of dp[k][y] s.t. a[i] % 7 = a[k] % 7 need to know max of dp[k][y] s.t. a[i] - 1 = a[k]

so 4 cases to consider when we update dp[i][y]