题解：光之大陆

一、题目分析

本题中光之大陆有(N)个种族，种族之间关系复杂，两个种族可以是盟友或非盟友。如果一系列种族中相邻种族以及首尾种族都是盟友，则构成一个联盟。合理的物种关系需满足任意两个种族之间都能通过盟友关系相连，且任意两个联盟没有共同种族。要求计算出(N)个种族满足条件的结盟关系的方案数对(M)取模的值。

二、解题思路

本题通过组合数学和动态规划的方法来求解。

（一）预处理部分（init函数）

1. 计算组合数：利用杨辉三角的性质(C[i][j] = C[i - 1][j - 1] + C[i - 1][j])（其中(C[i][j])表示从(i)个元素中选(j)个元素的组合数），通过二重循环计算出所有(0\leq j\leq i\leq n)的组合数(C[i][j])，并对(m)取模。
2. 计算阶乘相关值：
   • 初始化(g[1]=1)，(g[3]=3)。
   • 对于(i\geq4)，通过(g[i] = g[i - 1] * i)计算(g[i])，表示(i)的阶乘对(m)取模的值，用于后续计算。

（二）动态规划部分

定义二维数组f[i][j]表示将(i)个种族划分成(j)个联盟的方案数。状态转移方程推导如下：
- 对于将(i)个种族划分成(j)个联盟的情况，考虑最后一个联盟。假设最后一个联盟包含(k)个种族（(1\leq k\leq i - j + 1)）。
- 先从(i - 1)个种族中选(k - 1)个种族与第(i)个种族组成最后一个联盟，方案数为(C[i - 1][k - 1])。
- 剩下(i - k)个种族划分成(j - 1)个联盟，方案数为(f[i - k][j - 1])。
- 对于这(k)个种族构成一个联盟，它们内部的结盟方案数为(g[k])。
- 因此，通过三重循环遍历(i)、(j)、(k)，根据上述分析更新f[i][j]：

for (int i = 1; i <= n; i ++ )
    for (int j = 1; j <= i; j ++ )
        for (int k = 1; k <= i - j + 1; k ++ )
            f[i][j] = (f[i][j] + f[i - k][j - 1] * (LL)C[i - 1][k - 1] * g[k]) % m;

（三）计算结果部分

• 首先，当只有一个联盟时，方案数为(g[n - 1])，因为可以将(n)个种族看作一个环进行排列（固定一个种族后，其余(n - 1)个种族全排列）。
• 然后，对于划分成(k)（(2\leq k\leq n)）个联盟的情况，方案数为f[n][k] * p，其中p表示将(k)个联盟进行全排列（因为联盟之间也有不同的排列顺序），初始(p = 1)，每次循环更新p = p * n % m。
• 最后将所有情况的方案数相加，并对(m)取模得到最终结果：

LL res = g[n - 1], p = 1;
for (int k = 2; k <= n; k ++ )
{
    res += f[n][k] * p;
    p = p * n % m;
}
cout << res % m << endl;

三、代码实现细节

（一）头文件与全局变量

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 210;

int n, m;
int C[N][N], g[N], f[N][N];

• 引入输入输出、字符串操作、标准输入输出和算法相关头文件。
• 定义常量N表示种族数量的上限。
• 定义变量n为种族数量，m为取模值。
• 定义二维数组C存储组合数，一维数组g存储阶乘相关值，二维数组f用于动态规划存储方案数。

（二）预处理函数init

void init()
{
    for (int i = 0; i <= n; i ++ )
        for (int j = 0; j <= i; j ++ )
            if (!j) C[i][j] = 1;
            else C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % m;

    g[1] = 1, g[3] = 3;
    for (int i = 4; i <= n; i ++ ) g[i] = g[i - 1] * i % m;
}

• 计算组合数并对(m)取模。
• 初始化并计算阶乘相关值(g[i])。

（三）main函数

int main()
{
    cin >> n >> m;
    init();

    f[0][0] = 1;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            for (int k = 1; k <= i - j + 1; k ++ )
                f[i][j] = (f[i][j] + f[i - k][j - 1] * (LL)C[i - 1][k - 1] * g[k]) % m;

    LL res = g[n - 1], p = 1;
    for (int k = 2; k <= n; k ++ )
    {
        res += f[n][k] * p;
        p = p * n % m;
    }

    cout << res % m << endl;

    return 0;
}

• 读取种族数量n和取模值m。
• 调用init函数进行预处理。
• 通过动态规划计算f[i][j]。
• 计算最终的方案数并输出对(m)取模的结果。

四、时间复杂度和空间复杂度

（一）时间复杂度

• 预处理部分：计算组合数的时间复杂度为(O(n^2))，计算阶乘相关值的时间复杂度为(O(n))，所以预处理总时间复杂度为(O(n^2))。
• 动态规划部分：三重循环计算f[i][j]，时间复杂度为(O(n^3))。
• 计算结果部分：循环计算不同联盟数量下的方案数，时间复杂度为(O(n))。
• 因此，总的时间复杂度为(O(n^3))。

（二）空间复杂度

代码中使用了三个二维数组C、f和一个一维数组g，大小分别为(O(n^2))、(O(n^2))和(O(n))，所以空间复杂度为(O(n^2))。