Bitwise Recurrence

Problem Description

A recurrence relation is an equation that defines each element of a sequence as a function of the preceding elements.

Consider the following recurrence:

• F[0] = a
• F[1] = b
• F[2] = c

For n ≥ 3,

F[n] = (F[n-1] | F[n-2]) ⊕ F[n-3]

where:

• | is the bitwise OR operator
• ⊕ is the bitwise XOR operator

Given four integers a, b, c, and n, compute the value of F[n] according to the recurrence relation.

Function Signature

def bitwiseRecurrence(a: int, b: int, c: int, n: int) -> int:

• a: an integer, initial value for F[0]
• b: an integer, initial value for F[1]
• c: an integer, initial value for F[2]
• n: the index for which you want to compute F[n]

Constraints

0 ≤ a, b, c ≤ 10**12  
0 ≤ n ≤ 10**12  

Example

Input:

(4, 1, 10, 4)

Output:

14

Explanation:

F[0] = 4  
F[1] = 1  
F[2] = 10  
F[3] = (F[2] | F[1]) ⊕ F[0] = (10 | 1) ⊕ 4 = 11 ⊕ 4 = 15  
F[4] = (F[3] | F[2]) ⊕ F[1] = (15 | 10) ⊕ 1 = 15 ⊕ 1 = 14  

---

7. HackTree

You are given a tree with n nodes. Each node has a value assigned with it. The cost of a path is defined as the summation of all the values assigned to nodes that belong to the path.
The root of the tree is node number 1.

Cost of path example

The cost of the path 6 -> 5 -> 3 -> 1 in the above tree is 42 + 31 + 20 + 10 = 103.

A Vertical Path in a tree is the path that is going up towards the root of the tree. It is not necessary for the path to end at the root.
Given a tree with n nodes and an integer k. Find the number of vertical paths such that the (cost of the path) % k = 0 where % represents the modulo operation.

Example

k = 2
tree =

There are a total of 8 vertical paths:

1. 1
2. 2
3. 4
4. 2 -> 1
5. 4 -> 1
6. 3
7. 3 -> 4
8. 3 -> 4 -> 1

But only (2 -> 1), (4 -> 1), (3 -> 4) have (cost of the path) % k = 0.
Hence the answer is 3.

Function Description

Complete the function countVerticalPaths in the editor below.

countVerticalPaths has the following parameters:

• cost: the array representing the value of each node.
• edge_nodes: number of nodes in the tree.
• edge_from: integer array where the iᵗʰ integer denotes one endpoint of the iᵗʰ edge.
• edge_to: integer array where the iᵗʰ integer denotes the other endpoint of the iᵗʰ edge.
• k: an integer

Returns

• int: the number of vertical paths with (cost of the path) % k = 0
  Note: The tests are generated in such a way that the returned value fits in int32

Constraints

• 1 ≤ n ≤ 2 * 10⁵
• 0 ≤ cost[i] ≤ 10⁸
• 1 ≤ k ≤ 10⁵

Input Format For Custom Testing

The first line contains one integer, n denoting the size of the cost array.

The next n lines contain elements of the cost array.

The next line contains two integers, n and m (where m = n - 1), denoting the number of nodes and number of roads respectively.

Each line i of the m subsequent lines (where 0 ≤ i < m) contains two integers, u and v, denoting that nodes u and v are connected via an edge.

The next line contains an integer denoting k.

Sample Case 0

Sample Input For Custom Testing

5         -> n = Size of Cost array.
1
2
2
1
2         -> cost = {1,2,2,1,2}
5 4       -> n = 5, m = 4
5 4
2 3
1 4
2 5
2         -> k = 2

Sample Output

6

Explanation

There are 6 vertical paths following the given condition:

These paths are:

1. 2
2. 5 -> 2
3. 4 -> 1
4. 3
5. 3 -> 2
6. 5

Hence the answer is 6.

我们长期稳定承接各大科技公司如TikTok、Google、Amazon等的OA笔试代写服务，确保满分通过。如有需求，请随时联系我们。

We consistently provide professional online assessment services for major tech companies like TikTok, Google, and Amazon, guaranteeing perfect scores. Feel free to contact us if you're interested.