Sequence Creation ARCRT SOLUTION Code Chef

by

Sequence Creation ARCRT SOLUTION Code Chef

Chef has two sequences of integers (A1,A2,…,AN)(A1,A2,…,AN) and (B1,B2,…,BN)(B1,B2,…,BN).

A sequence of integers is beautiful if it contains only distinct integers. For each valid ii:

  • Chef wants to create a beautiful sequence SiSi. Let’s denote the length of this sequence by LiLi and the sequence by Si,1,Si,2,…,Si,LiSi,1,Si,2,…,Si,Li.
  • The sequence SiSi is good if for each valid jj, Si,jSi,j is either equal to Ai+j−1Ai+j−1 or Bi+j−1Bi+j−1. Note that this means LiLi must be at most N−i+1N−i+1.
  • Let’s denote the maximum possible value of LiLi (the maximum value such that some good sequence SiSi with this length exists) by MiMi.
  • Help Chef find the number of good sequences SiSi that have the maximum possible length MiMi. Since this number may be enormous, compute it modulo 109+7109+7.

Input

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains a single integer NN.
  • The second line contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN.
  • The third line contains NN space-separated integers B1,B2,…,BNB1,B2,…,BN.

Output

For each test case, print a single line containing NN space-separated integers. For each valid ii, the ii-th of these integers should be the number of possible sequences SiSi modulo 109+7109+7.

Constraints

  • 1≤T≤1,0001≤T≤1,000
  • 1≤N≤1051≤N≤105
  • |Ai|,|Bi|≤109|Ai|,|Bi|≤109 for each valid ii
  • the sum of NN over all test cases does not exceed 5⋅1055⋅105

Subtasks

Subtask #1 (20 points):

  • N≤1,000N≤1,000
  • the sum of NN over all test cases does not exceed 5⋅1035⋅103

Subtask #2 (80 points): original constraints

Example Input

2
4
2 2 3 2
2 3 4 4
5
1 2 2 3 3
2 1 2 3 1

Example Output

1 2 3 2
2 1 1 1 2

Explanation

Example case 1:

  • S1S1 can only be (2,3,4)(2,3,4).
  • S2S2 can be (2,3,4)(2,3,4) or (3,4,2)(3,4,2).
  • S3S3 can be (3,2)(3,2), (3,4)(3,4) or (4,2)(4,2).
  • S4S4 can be (2)(2) or (4)(4).

Example case 2:

  • S1S1 can be (1,2)(1,2) or (2,1)(2,1).
  • S2S2 can only be (1,2,3)(1,2,3).
  • S3S3 can only be (2,3,1)(2,3,1).
  • S4S4 can only be (3,1)(3,1).
  • S5S5 can be (3)(3) or (1)(1).

Solution

January Long Challenge 2021

Leave a Comment