A. Two Regular Polygons

以 $n$ 多边形的顶点为点，是否可以画出 $m$ 多边形，显然，只需要满足 $m \mid n$.

# include <iostream>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        if (n % m)
            cout << "NO" << endl;
        else
            cout << "YES" << endl;
    }
    return 0;
}

B. Bogosort

由于下标一定是递增的，所以我们将数组 $a$ 降序排序，看是否满足要求。

用反证法证明这一点，假设存在 $i, j (i < j)$，使得 $j - a_j = i - a_i$.

由于事先按照降序排序了，所以 $a_i \geq a_j$，我们分情况来讨论：

1. $a_i = a_j:$ 当满足 $j - a_j = i - a_i$ 时需要满足 $i = j$，产生矛盾。
2. $a_i > a_j:$ 当满足 $j - a_j = i - a_i$ 时需要满足 $i > j$，产生矛盾。

综上，只需要将数组 $a$ 降序排序后输出即可。

# include <iostream>
# include <algorithm>

using namespace std;

const int N = 110;
int n, F[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 0; i < n; i++)
            cin >> F[i];
        sort(F, F + n);
        reverse(F, F + n);
        for (int i = 0; i < n; i++)
            cout << F[i] << ' ';
        cout << endl;
    }
    return 0;
}

C. Adding Powers

我们来考虑与题意对称的操作：每次可以选择任意位置减去 $k^i$，是否能将给定的数组 $a$ 的每个元素都变为 $0$.

当 $k = 1$ 时可以发现这是一个特殊情况，即：进行 $\sum_{i = 1}^{n}{a_i}$ 次操作，一定可以实现目的。（写完之后突然想起来自己代码里没有体现这一点为啥 $AC$ 了~，然后发现题目要求的 $k$ 的最小值为 $2$ ，嘤嘤嘤，白打了那么多字)

由于 $2^{54}$ 就超过了 $10^{16}$，所以操作次数最多就是 $54$ 次，从 $k ^ 0$ ~ $k ^ {pos} (pos + 1 = 54 \vee (k ^ {pos} <= 10^{16} \wedge k^{pos + 1} > 10^{16}))$.

数据范围很小，所以可以在将上述的 $k^i$ 次方求出来之后，枚举数组 $a$ 中的元素，再从高次往低次枚举次方数，只要该数组元素减完当前枚举的值之后仍然非负就减，最后判断数组中是否全为 $0$ 即可。

下面自问自答一下在写题解时突发奇想的问题：

• 为什么要从高次往低次枚举次方数？

参照一个数拆成 $2$ 进制数时的从高次往低次判是否为 $1$ 的做法。如果反过来枚举会出现矛盾，比如题目样例 $1$ 的最后一个数据，具体证明不再赘述。

• 能否先将 $a$ 数组求和，然后判断和是否可以拆解成 $k$ 进制？

直接给一组数据证明不能先求和。

$n = k = 2, a_1 = a_2 = 1$

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

using namespace std;

typedef long long LL;
const int N = 54;
int n, k;
LL a[N], K[N];
bool vis[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        memset(vis, false, sizeof vis);
        cin >> n >> k;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        K[0] = 1;
        int pos = 1;
        while (pos < N && K[pos - 1] <= 1e16) {
            K[pos] = K[pos - 1] * k;
            pos++;
        }
        if (K[pos - 1] > 1e16)
            pos--;
        bool success = true;
        for (int i = 1; i <= n; i++) {
            for (int j = pos - 1; ~j; j--)
                if (!vis[j] && a[i] >= K[j]) {
                    vis[j] = true;
                    a[i] -= K[j];
                }
            if (a[i]) {
                success = false;
                break;
            }
        }
        cout << (success ? "YES" : "NO") << endl;
    }
    return 0;
}

D. Count the Arrays

组合数问题。

首先可以发现，当 $n = 2$ 时无论怎么取值都不能满足题意，直接输出 $0$ 即可。

接下来讨论 $n > 2$ 的情况：

由于题意要求选出的数要先严格递增，再严格递减，所以我们可以枚举顶点的数是多少，即枚举数列中的最大值。不难发现，这个最大值的取值范围为 $n - 1$ ~ $m$.

假设当前选择的最大值为 $k$，那么，我们需要在小于 $k$ 的数中选出 $n - 2$ 个数作为剩余项，即选出 $C_{k - 1}^{n - 2}$ 个数。

接着需要确定哪个数出现了两次，这里存在 $n - 2$ 种情况。

最后就是如何排列这些数，使其满足题意。

首先出现两次的数一定在最大值两侧，而最大值出现的位置有 $n - 2$ 种选择，即：它可以出现在第 $2, 3, …, n - 1$ 个位置。

• 当出现在第 $2$ 个位置时，在这个数左侧不需要再选择数字，就是说需要在剩余 $n - 3$ 个数字中选择 $0$ 个，即：$C_{n - 3}^0$.
• 当出现在第 $3$ 个位置时，在这个数左侧需要再选择 $1$ 个数字，即：$C_{n - 3}^1$.
• ......
• 当出现在第 $n - 1$ 个位置时，在这个数左侧需要再选择 $n - 3$ 个数字，即：$C_{n - 3}^{n - 3}$.

即：排列这些数字的方法有
$$ \sum_{i = 0}^{n - 3}{C_{n - 3}^i} = 2 ^ {n - 3} $$
综上，本题所求即为下述公式的结果：
$$ \sum_{k = n - 1}^{m}{C_{k - 1}^{n - 2}} \cdot (n - 2) \cdot 2^{n - 3} $$

# include <iostream>

using namespace std;

typedef long long LL;
const int N = 2e5 + 5, mod = 998244353;
LL F[N], G[N];

LL quickpow(LL a, LL b)
{
    LL res = 1;
    while (b) {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

void init()
{
    F[0] = G[0] = 1;
    for (int i = 1; i < N; i++) {
        F[i] = F[i - 1] * i % mod;
        G[i] = G[i - 1] * quickpow(i, mod - 2) % mod;
    }
    return;
}

LL C(int n, int k)
{
    return F[n] * G[k] % mod * G[n - k] % mod;
}

int main()
{
    init();
    int n, m;
    cin >> n >> m;
    if (n == 2)
        cout << 0 << endl;
    else {
        LL res = 0;
        for (int i = n - 2; i < m; i++)
            res = (res + C(i, n - 2)) % mod;
        cout << res * (n - 2) % mod * quickpow(2, n - 3) % mod << endl;
    }
    return 0;
}

E. Array Shrinking

不论先合成哪两个数，都有可能对后续的合成造成影响，而这题数据范围又比较小，所以考虑一下能否以某种方式枚举所有情况。

尝试着用动态规划来解决此题。

定义 $dp[len]$ 表示为：所有只考虑前缀长度为 $len$ 的融合方案的集合。属性为融合后剩余数的个数的最小值。

接下来考虑这个状态可以用来更新后续的哪些状态，对于后续的起始点 $l = len + 1$ 与终点 $r \in [len + 1, n]$ 而言，如果 $l$ ~ $r$ 这一段在融合后剩余的数的个数不止一个，那么这段区间 $l$ ~ $r$ 必定可以分成对应的份数，使每份各自融合后剩余的数的个数只有一个，而这种情况显然是会被枚举到的，所以我们只需要用 $dp[len]$ 来更新所有闭区间 $[l, r]$ 融合后剩余数的个数为一个的状态，即：$dp[r] = min(dp[r], dp[len] + 1)$.

现在的问题就转化为如何求出一段区间 $[l, r]$ 能否融合成一个数，我们可以将这一段区间拆分成两段考虑，即考虑所有的 $mid, mid \in [l, r)$，如果两段区间 $[l, mid], [mid + 1, r]$ 能够融合成相同的一个数，则整段区间最终也可以融合成一个数。这个操作可以事先用记忆化搜索的递归处理出来。

至此，就可以顺利 $AC$ 此题，最终答案即为 $dp[n]$.

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

using namespace std;

const int N = 510;
int n, a[N];
int ans[N], dp[N][N];

int get_dp_l_r(int l, int r)
{
    if (l == r)
        dp[l][r] = a[l];
    if (dp[l][r])
        return dp[l][r];
    dp[l][r] = -1;
    for (int mid = l; mid < r; mid++) {
        int l_val = get_dp_l_r(l, mid);
        int r_val = get_dp_l_r(mid + 1, r);
        if (l_val != -1 && l_val == r_val)
            return dp[l][r] = l_val + 1;
    }
    return dp[l][r];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    get_dp_l_r(1, n);
    memset(ans, 0x3f, sizeof ans);
    ans[0] = 0;
    for (int len = 0; len < n; len++)
        for (int l = len + 1, r = l; r <= n; r++)
            if (dp[l][r] != -1)
                ans[r] = min(ans[r], ans[len] + 1);
    cout << ans[n] << endl;
    return 0;
}

F. Attack on Red Kingdom

这题像是博弈论，然而蒟蒻并不会，等以后变强了再补。如果我没遗忘的话

G. Autocompletion

有一说一，光看这篇英文题目搞懂字符串咋来的就花了好长时间，然后到死都没想明白样例是咋回事，果然蒟蒻还是蒟蒻，高分题不适合自己，嘤嘤嘤，等以后变强了再补。如果我还记得的话