Page Contents
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
- Chef and Division 3 DIVTHREE SOLUTION Code Chef
- Encoded String DECODEIT SOLUTION Code Chef
- Point Of Impact BILLRD SOLUTION Code Chef
- Fair Elections FAIRELCT SOLUTION Code Chef
- Watching CPL WIPL SOLUTION Code Chef
- Chef and Ants ANTSCHEF SOLUTION Code Chef
- Blackjack BLKJK SOLUTION Code Chef
- And-Or Game ORAND SOLUTION Code Chef
- Stack-Queue Sort (Challenge) SQSORT SOLUTION Code Chef
- Expected Number of SCCs RCTEXSCC SOLUTION Code Chef
- Curious Matrix CURMAT SOLUTION Code Chef
- Cool Subsets COOLSBST SOLUTION Code Chef
- Sequence Creation ARCRT SOLUTION Code Chef
- Greedy Students GRDSTD SOLUTION Code Chef