[涂色] #algorithm

涂色问题.md

一个圆盘，分成N块，有M种涂色方案，要求相邻两块不可同色，有多少种涂色方案。

A(N)可以看成第一块M种和剩下的M-1块又N-1种涂色方案，但是包含了第一块和最后一块同色的情况，即A(N-1) A(N) = M * (M-1)^N-1 - A(N-1)

import math


def vender(N, M):  # N块， M种涂色方案
    if N == 1:
        return M
    if N == 2:
        return M * (M-1)
    return int(M * math.pow(M-1, N-1) - vender(N-1, M))


while True:
    a = []
    line = input()
    for x in line.split():
        a.append(int(x))
    print(vender(a[0], a[1]))