ACM模版

##描述

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

首先我们考虑不是环的情况，也就是说 A A A 和 E E E 断开的情况下， A A A 可以填入 n n n 种颜色，然后剩下的 m − 1 m - 1 m−1 个都只能填入 n − 1 n - 1 n−1 种，所以总情况数为 n ∗ ( n − 1 ) m − 1 n * (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 − 1 C(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)。

于是可以递归求解该题。

当然，这个题还可以用 d f s dfs dfs 来解。

##代码

#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;
}

最后答案为： 240 240 240。