Problem name: Quantum Entanglement Network Query System

Topic: Advanced Graph Theory, Matrix Exponentiation, Number Theory, Dynamic

Programming
Tags: Graph Theory, Matrix Operations, Modular Arithmetic, Path Counting, Multi-dimensional
DP
Level: Hard
Language used: Python

Problem Statement
In a quantum computing research facility, qubits are connected in an entanglement network.
The facility needs to analyze "Quantum Coherence Paths" - special paths where quantum
information can propagate with specific mathematical properties.

A Quantum Coherence Path has these properties:

1. It must have exactly K edges (fixed path length)

2. The product of edge weights along the path must be divisible by a prime P
3. The path can revisit nodes (cycles allowed)
4. The XOR of all node values along the path (including start and end) must equal a target
value X

The Query Complexity Score for a given configuration is calculated as:

(Count of valid K-length paths from node S) × (Sum of products of edge weights for all valid
paths mod M) + (Number of distinct nodes visited across all valid paths)

You must handle three types of operations:

1. Update Node Value: 1 u new_value - Change the value stored at node u

2. Update Edge Weight: 2 u v new_weight - Change the weight of edge u->v
3. Coherence Query: 3 S K P X - Calculate Query Complexity Score starting from node
S, with path length K, divisibility prime P, and target XOR value X

Example
Consider nodes {1, 2, 3} with values [5, 3, 7] and edges:

● Edge (1=>2): weight=6

● Edge (2=>3): weight=10
● Edge (3=>1): weight=15
 ● Edge (2=>1): weight=4

Query: S=1, K=2, P=2, X=6, M=10^9+7

Analysis:

Find all paths of length 2 from node 1:

Path 1->2->3:

● Product = 6 × 10 = 60, divisible by 2 ✓

● XOR = 5 ⊕ 3 ⊕ 7 = 1 ✗ (not equal to 6)

Path 1->2->1:

● Product = 6 × 4 = 24, divisible by 2 ✓

● XOR = 5 ⊕ 3 ⊕ 5 = 5 ✗

No valid paths satisfy both conditions.

Input Format
First line: N E Q M (1 ≤ N ≤ 100, 1 ≤ E ≤ 500, 1 ≤ Q ≤ 500, M = 10^9+7)
Second line: N integers representing initial node values (0 ≤ value ≤ 1000)
Next E lines: u v w (directed edge from u to v with weight w, 1 ≤ w ≤ 100)
Next Q lines: Query operations

Output Format
For each type 3 query, output the Query Complexity Score modulo M

Constraints
● 1 ≤ N ≤ 100
● 1 ≤ E ≤ 500
● 1 ≤ Q ≤ 500
● 1 ≤ K ≤ 10
● 2 ≤ P ≤ 97 (P is always prime)
● 0 ≤ X ≤ 1023
● 1 ≤ w ≤ 100
● 0 ≤ node_value ≤ 1000
Sample Test Case 1
Input
3 4 1 1000000007
537
126
2 3 10
3 1 15
214
31226

Output
0

Explanation
Initial Configuration:

● Nodes: 1(value=5), 2(value=3), 3(value=7)

● Edges: 1->2(weight=6), 2->3(weight=10), 3->1(weight=15), 2->1(weight=4)

Query: type=3, S=1, K=2, P=2, X=6

Find all paths of length K=2 from node 1:

Path 1->2->3:

● Product: 6 × 10 = 60
● 60 % 2 = 0 ✓ (divisible by prime 2)
● XOR: 5 ⊕ 3 ⊕ 7 = 1
● 1 ≠ 6 ✗ (INVALID - XOR doesn't match target)

Path 1->2->1:

● Product: 6 × 4 = 24
● 24 % 2 = 0 ✓ (divisible by prime 2)
● XOR: 5 ⊕ 3 ⊕ 5 = 5
● 5 ≠ 6 ✗ (INVALID - XOR doesn't match target)

Result:

● Valid paths count: 0

● Sum of products: 0
● Distinct nodes visited: 0
 ● Score = (0 × 0) + 0 = 0

Sample Test Case 2

Input
4 5 2 1000000007
1234
124
236
342
413
138
31220
31226

Output
27

19

Explanation
Initial Configuration:

● Nodes: 1(value=1), 2(value=2), 3(value=3), 4(value=4)

● Edges: 1->2(4), 2->3(6), 3->4(2), 4->1(3), 1->3(8)

Query 1: type=3, S=1, K=2, P=2, X=0

Find all paths of length 2 from node 1:

Path 1->2->3:

● Product: 4 × 6 = 24
● 24 % 2 = 0 ✓
● XOR: 1 ⊕ 2 ⊕ 3 = 0 ✓ (VALID!)
● Visited nodes: {1, 2, 3}

Path 1->3->4:

● Product: 8 × 2 = 16
● 16 % 2 = 0 ✓
 ● XOR: 1 ⊕ 3 ⊕ 4 = 6 ✗ (INVALID)

Result:

● Valid paths count: 1

● Sum of products: 24
● Distinct nodes: {1, 2, 3} = 3 nodes
● Score = (1 × 24) + 3 = 27

Query 2: type=3, S=1, K=2, P=2, X=6

Find all paths of length 2 from node 1:

Path 1->2->3:

● Product: 4 × 6 = 24
● 24 % 2 = 0 ✓
● XOR: 1 ⊕ 2 ⊕ 3 = 0 ✗ (INVALID)

Path 1->3->4:

● Product: 8 × 2 = 16
● 16 % 2 = 0 ✓
● XOR: 1 ⊕ 3 ⊕ 4 = 6 ✓ (VALID!)
● Visited nodes: {1, 3, 4}

Result:

● Valid paths count: 1

● Sum of products: 16
● Distinct nodes: {1, 3, 4} = 3 nodes
● Score = (1 × 16) + 3 = 19

Code
import sys
from collections import defaultdict, deque

MOD = 10**9 + 7

class QuantumNetwork:
def __init__(self, n, node_values):
self.n = n
self.node_values = [0] + node_values # 1-indexed
[Link] = defaultdict(list) # edges[u] = [(v, weight), ...]

def add_or_update_edge(self, u, v, w):

"""Add or update edge from u to v"""
# Remove existing edge if present
 [Link][u] = [(dest, weight) for dest, weight in [Link][u] if dest != v]
# Add new edge
[Link][u].append((v, w))

def update_node_value(self, u, new_value):

"""Update node value"""
self.node_values[u] = new_value

def find_paths_dfs(self, current, start, k_remaining, current_product, current_xor,

visited_nodes, path_products, all_visited):
"""DFS to find all K-length paths with required properties"""
if k_remaining == 0:
return [(current_product, current_xor, visited_nodes.copy())]

results = []
for neighbor, weight in [Link][current]:
new_product = (current_product * weight) % MOD
new_xor = current_xor ^ self.node_values[neighbor]
new_visited = visited_nodes.copy()
new_visited.add(neighbor)

[Link](self.find_paths_dfs(
neighbor, start, k_remaining - 1, new_product,
new_xor, new_visited, path_products, all_visited
))

return results

def calculate_coherence(self, S, K, P, X):

"""Calculate Query Complexity Score"""
# Find all K-length paths from S
initial_xor = self.node_values[S]
initial_visited = {S}

all_paths = self.find_paths_dfs(
S, S, K, 1, initial_xor, initial_visited, [], set()
)

# Filter valid paths

valid_count = 0
sum_products = 0
all_distinct_nodes = set()

for product, xor_val, visited in all_paths:

if product % P == 0 and xor_val == X:
valid_count += 1
sum_products = (sum_products + product) % MOD
all_distinct_nodes.update(visited)

distinct_count = len(all_distinct_nodes)
 # Calculate score
score = (valid_count * sum_products + distinct_count) % MOD

return score

def main():
input_data = [Link]().strip().split()
idx = 0

n = int(input_data[idx])
e = int(input_data[idx + 1])
q = int(input_data[idx + 2])
m = int(input_data[idx + 3])
idx += 4

# Read node values

node_values = []
for i in range(n):
node_values.append(int(input_data[idx]))
idx += 1

network = QuantumNetwork(n, node_values)

# Read initial edges

for _ in range(e):
u = int(input_data[idx])
v = int(input_data[idx + 1])
w = int(input_data[idx + 2])
idx += 3
network.add_or_update_edge(u, v, w)

# Process queries
results = []
for _ in range(q):
query_type = int(input_data[idx])
idx += 1

if query_type == 1:
# Update node value
u = int(input_data[idx])
new_value = int(input_data[idx + 1])
idx += 2
network.update_node_value(u, new_value)
elif query_type == 2:
# Update edge weight
u = int(input_data[idx])
v = int(input_data[idx + 1])
new_weight = int(input_data[idx + 2])
idx += 3
network.add_or_update_edge(u, v, new_weight)
else:
 # Coherence query (type 3)
S = int(input_data[idx])
K = int(input_data[idx + 1])
P = int(input_data[idx + 2])
X = int(input_data[idx + 3])
idx += 4
result = network.calculate_coherence(S, K, P, X)
[Link](result)

for result in results:

print(result)

if __name__ == "__main__":
main()

One Compiler Link

[Link]