有4种颜色，填入5个组成环的块中

描述

描述

##题解 这个题按题意应该是不用考虑置换群的，一道数论题。

首先我们考虑不是环的情况，也就是说 AAA 和 EEE 断开的情况下，AAA 可以填入 nnn 种颜色，然后剩下的 m−1m - 1m−1 个都只能填入 n−1n - 1n−1 种，所以总情况数为 n∗(n−1)m−1n * (n - 1)^{m - 1}n∗(n−1)m−1。

这时我们来考虑环的情况，环的情况的话在链的基础上需要考虑首尾是否相同，设首尾相同的情况数为 A(m)A(m)A(m)，不同的情况数为 B(m)B(m)B(m)，设所有情况为 C(m)C(m)C(m)，已知 C(m)=A(m)+B(m)=n∗(n−1)m−1C(m) = A(m) + B(m) = n * (n - 1)^{m - 1}C(m)=A(m)+B(m)=n∗(n−1)m−1。另外当首尾相同时，我们可以将首尾看做同一块，那么 A(m)=B(m−1)A(m) = B(m - 1)A(m)=B(m−1)，所以 C(m)=B(m−1)+B(m)C(m) = B(m - 1) + B(m)C(m)=B(m−1)+B(m)，继而可得 B(m)=C(m)−B(m−1)=n∗(n−1)m−1−B(m−1)B(m) = C(m) - B(m - 1) = n * (n - 1)^{m - 1} - B(m - 1)B(m)=C(m)−B(m−1)=n∗(n−1)m−1−B(m−1)。

于是可以递归求解该题。

当然，这个题还可以用 dfsdfsdfs 来解。

##代码

#include <iostream>
#include <cmath>

using namespace std;

int n, m;

long long B(int m)
{
    if (m == 1)
    {
        return 0;
    }
    long long t = n * pow(n - 1, m - 1);
    return t - B(m - 1);
}

long long solve(int n, int m)
{
    if (m == 1)
    {
        return n;
    }
    else
    {
        return B(m);
    }
}

int main()
{
    n = 4;
    m = 5;
    
    cout << solve(4, 5) << '\n';
    
    return 0;
}

最后答案为：240240240。