↓Skip to main content
  1. Posts/

LeetCode-3393 统计异或值为给定值的路径数目

·1 min·
Table of Contents

LeetCode-3393 统计异或值为给定值的路径数目 #

Solution 1 #

动态规划, 设 $f(i, j, s)$ 表示从 $(0, 0)$ 到 $(i, j)$ 的异或和为 $s$ 的路径数目.

代码如下:

class Solution:
    def countPathsWithXorValue(self, grid: List[List[int]], k: int) -> int:
        MOD = 1_000_000_007
        m, n = len(grid), len(grid[0])

        @cache 
        def f(i, j, s):
            if i == 0 and j == 0:
                return int(s == grid[0][0])
            res = 0
            if i != 0:
                res = (res + f(i - 1, j, s ^ grid[i][j])) % MOD
            if j != 0:
                res = (res + f(i, j - 1, s ^ grid[i][j])) % MOD
            return res
            
        return f(m - 1, n - 1, k)