3.12 美团笔试

def dfs(pb, i, j, n, res):
    if j == n-1:
        if i == 1:
            res[0] += 1
        return

    for ne in get_neigh(i, j, n):
        if pb[ne[0]][ne[1]]:
            pb[ne[0]][ne[1]] == False
            dfs(pb, ne[0], ne[1], n, res)
            pb[ne[0]][ne[1]] == True

def get_neigh(i, j, x):
    neigh = []
    if j+1 < x:
        neigh.append([i, j+1])
    if j+1 < x and i == 0:
        neigh.append([i+1, j+1])
    if j+1 < x and i == 1:
        neigh.append([i-1, j+1])
    return neigh


if __name__ == '__main__':
    n = int(input())
    p = []
    p.append(list(input()))
    p.append(list(input()))
    pb = [[True for i in range(n)] for i in range(2)]
    for i in range(2):
        for j in range(n):
            if p[i][j] != '.':
                pb[i][j] = False
    pb[0][0] = False
    res = [0]
    dfs(pb, 0, 0, n, res)

    res = res[0] if res[0] > 0 else -1
    print(res)

    

if __name__ == '__main__':
    n = int(input())
    p = []
    p.append(list(input()))
    p.append(list(input()))
    dp = [[0 for i in range(n)] for i in range(2)]
    pb = [[True for i in range(n)] for i in range(2)]
    for i in range(2):
        for j in range(n):
            if p[i][j] != '.':
                pb[i][j] = False
    dp[-1][-2] = 1 if pb[-1][-2] else 0
    dp[-2][-2] = 1 if pb[-2][-2] else 0 
    
    for j in range(-3, -n-1, -1):
        for i in range(-1, -3, -1):
            if pb[i][j]:
                if i == -1:
                    dp[i][j] = dp[i-1][j+1] + dp[i][j+1]
                if i == -2:
                    dp[i][j] = dp[i][j+1] + dp[i+1][j+1]

    res = dp[0][0] if dp[0][0] > 0 else -1
    print(res)

from itertools import product

n, k, l, r = tuple(map(int, input().split()))
f = list(range(l, r+1))
t = tuple((f for i in range(n)))
a = product(*t)
res = 0
for i in a:
    if sum(i) % k == 0:
        res += 1
print(res)