Page Contents
Sequence Creation ARCRT SOLUTION Code Chef
Chef has two sequences of integers (A1,A2,…,AN) and (B1,B2,…,BN).
A sequence of integers is beautiful if it contains only distinct integers. For each valid i:
Chef wants to create a beautiful sequence Si. Let’s denote the length of this sequence by Li and the sequence by Si,1,Si,2,…,Si,Li.
The sequence Si is good if for each valid j, Si,j is either equal to Ai+j−1 or Bi+j−1. Note that this means Li must be at most N−i+1.
Let’s denote the maximum possible value of Li (the maximum value such that some good sequence Si with this length exists) by Mi.
Help Chef find the number of good sequences Si that have the maximum possible length Mi. Since this number may be enormous, compute it modulo 109+7.
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.Sequence Creation ARCRT SOLUTION
The first line of each test case contains a single integer N.
The second line contains N space-separated integers A1,A2,…,AN.
The third line contains N space-separated integers B1,B2,…,BN.
Output
For each test case, print a single line containing N space-separated integers. For each valid i, the i-th of these integers should be the number of possible sequences Si modulo 109+7.Sequence Creation ARCRT SOLUTION
Constraints
- 1≤T≤1,000
- 1≤N≤105
- |Ai|,|Bi|≤109 for each valid i
- the sum of N over all test cases does not exceed 5⋅105
Subtasks
Subtask #1 (20 points):
- N≤1,000
- the sum of N over all test cases does not exceed 5⋅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:
- S1 can only be (2,3,4).
- S2 can be (2,3,4) or (3,4,2).
- S3 can be (3,2), (3,4) or (4,2).
- S4 can be (2) or (4).
Example case 2:
- S1 can be (1,2) or (2,1).
- S2 can only be (1,2,3).
- S3 can only be (2,3,1).
- S4 can only be (3,1).
- S5 can be (3) or (1).
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
6 thoughts on “Sequence Creation ARCRT SOLUTION Code Chef”