2024牛客暑期多校训练营2

难度梯度 ECH BIA GDJ F

A Floor Tiles

题意

有 \(A\)，\(B\) 两种地板，给你 \(n*m\) 的一个矩阵，每个格子可以放一块地板，

刚开始 \((x,y)\) 放了一块 \(ch\) 地板，

问你怎么放置，能使得恰好有 \(k\) 根曲线。

解题思路

刚开始我们先全放 \(A\) 或全放 \(B\)，我们会发现一定恰好有 \(n+m\) 根曲线。

然后我们可以发现，最外围随便怎么放，都会有 \(n+m\) 根曲线，所以我们能构成的曲线的数量至少为 \(n+m\)。

当 \(k<n+m\) 时，一定无解。

然后我们需要看怎样构造能让曲线变多，可以容易发现，单位圆为最优的构造方式，

然后根据最开始放的地板，假装全放 \(ch\)，然后构造单位圆即可，

我们需要注意 \((x,y)\) 必须放 \(ch\)，所以我们通过 \(x+y\) 的奇偶性，来确定具体放什么。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
vector<string> get(int n, int m, int k, int x, int y, char ch) {
    vector ans(n, string(m, ch));
    int p = ((x + y) % 2) ^ (ch - 'A');
    for (int i = 1 ; i < n ; i++) {
        for (int j = 1 ; j < m ; j++) {
            if (k > 0 && (i + j) % 2 == p) {
                k--;
                ans[i - 1][j] = ans[i][j - 1] = 'B';
                ans[i][j] = ans[i - 1][j - 1] = 'A';
            }
        }
    }
    if (k > 0) {
        return {};
    }
    return ans;
}
void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    int x, y;
    char ch;
    cin >> x >> y >> ch;
    x--;
    y--;
    k -= n + m;
    if (k < 0) {
        cout << "No\n";
        return;
    }
    vector<string> ans = get(n, m, k, x, y, ch);
    if (ans.empty()) {
        cout << "No\n";
        return;
    }
    cout << "Yes\n";
    for (auto &x : ans) {
        cout << x << "\n";
    }
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

B MST

题意

\(n\) 个点 \(m\) 条边的带权无向图，保证不存在自环。

\(q\) 次询问，每次询问给出 \(k\) 个点，问这 \(k\) 个点的最小生成树的权值，没有则为 \(-1\)。

\(sum(k)\le 10^5\)

解题思路

我们离线查询，首先存下所有的边，和查询的点集。

对每个查询单据建立并查集，这里需要用 map 存储，并在输入的时候初始化。

\(qr_x\) 表示查询中含有 \(x\) 的查询编号。

然后我们对边的权重从小到大进行排序，然后按顺序依次枚举所有边，

取 \(u,v,w\) 为每次边的两个节点和边的权重，

我们需要取 \(qr_u\) 和 \(qr_v\)，如果一个查询同时出现在这两个中，说明这个边在这个查询中。

如果这两个点在这个查询中已经是连通块了，就跳过，否则使他们联通，并累加权值和点的个数。

这里使用单调优化，定两个指针 \(P1,P2\)，如果 \(qr_{u,p1}>qr_{v,p2}\) 那么我们需要 \(qr_v\) 更大才可能使得两者相等，所以 \(p2++\)，相反则 \(p1++\)，相等则如上述说明，这个边在这个查询中。

复杂度证明，首先对边排序是 \(O(m\log m)\)

然后我们考虑让点分配均匀，也就是一共 \(\sqrt(n)\) 次询问，每次询问 \(\sqrt(n)\) 个点。

那么最后枚举所有边的时间复杂度为 \(O(m*\sqrt(n)*\log n)\) 。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
unordered_map<int, int> adj[100005];
array<int, 3> edges[100005];
unordered_map<int, int> f[100005];
vector<int> a[100005], qr[100005];
i64 ans[100005];
int cnt[100005];
int find(int idx, int x) {
    return f[idx][x] == x ? x : f[idx][x] = find(idx, f[idx][x]);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1 ; i <= m ; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        if (u > v) {
            swap(u, v);
        }
        if (adj[u].count(v)) {
            w = min(w, adj[u][v]);
        }
        adj[u][v] = w;
    }
    int tot1 = 0;
    for (int u = 1 ; u <= n ; u++) {
        for (auto &[v, w] : adj[u]) {
            edges[tot1++] = {u, v, w}; 
        }
    }
    sort(edges, edges + tot1, [&](const auto &x, const auto &y) {
        return x[2] < y[2];
    });
    for (int i = 0  ; i < tot1 ; i++) {
        auto [u, v, w] = edges[i];
    }
    for (int i = 1 ; i <= q ; i++) {
        int k;
        cin >> k;
        a[i].resize(k);
        for (int j = 0 ; j < k ; j++) {
            int x;
            cin >> x;
            f[i][x] = x;
            qr[x].push_back(i);
        }
    }
    for (int i = 0 ; i < tot1 ; i++) {
        auto [u, v, w] = edges[i];
        int P1 = 0, P2 = 0;
        int n1 = qr[u].size(), n2 = qr[v].size();
        while (P1 < n1 && P2 < n2) {
            int x = qr[u][P1], y = qr[v][P2];
            if (x > y) {
                P2++;
                continue;
            }
            if (x < y) {
                P1++;
                continue;
            }
            if (x == y) {
                int tu = find(x, u);
                int tv = find(y, v);
                if (tu != tv) {
                    f[x][tu] = tv;
                    ans[x] += w;
                    cnt[x]++;
                }
                P1++;
                P2++;
            }
        }
    }
    for (int i = 1 ; i <= q ; i++) {
        if (cnt[i] != (int) a[i].size() - 1) {
            ans[i] = -1;
        }
        cout << ans[i] << "\n";
    }
    return 0;
}

C Red Walking on Grid

题意

有一个 \(2*n\) 的矩阵，分别有字符 'R' 和 'W'。

你可以任意选一个字符 'R' 作为起点，

每次操作，你可以选择一个相邻的字符为 'R' 的格子，然后走到格子上，

当你离开一个有字符 'R' 的格子，这个字符变为 'W'，

问你最多可能操作多少次。

解题思路

首先只有两行，假设我们不向左走，

那么我们只可能有四种走法，

① 在第一行的格子直接往右走。

② 在第一行的格子先向下走再向右走。

③ 在第二行的格子直接往右走。

④ 在第二行的格子先向上走再向右走。

定义 \(dp_{i,j]\) 为在第 \(i\) 列第 \(j\) 行时，往上下右方向走过的最大步数。

这样如果我们从第一列开始走，使用动态规划就能推出，起点在第一列的答案。

只要我们每一列都初始化，就可以做到起点任意了。

需要注意到的是，\(dp\) 数组是到达这个点的最大步数，

这个时候我们没有往上下走，

如果此时可以上下走，那么我们答案就会减少，

所以我们递推完之后再 check 一遍加上即可。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
char mp[1000005][3];
int dp[1000005][3]; //0 上 1 下
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>> n ;
    for(int i = 1 ; i <= 2 ; i++){
        for(int j = 1 ; j <= n ; j++){
            cin >> mp[j][i];
        }
    }
    for (int i = 1 ; i <= n ; i++) {
        if (mp[i][1] == 'R') {
            dp[i][1] = max(dp[i - 1][1], 1);
        }
        if (mp[i][2] == 'R') {
            dp[i][2] = max(dp[i - 1][2], 1);
        }
        { // 上 -> 下右
            if (mp[i - 1][1] == 'R' && mp[i - 1][2] == 'R' && mp[i][2] == 'R') {
                dp[i][2] = max(dp[i][2], dp[i - 1][1] + 2);
            }
        }
        { // 上 -> 右
            if (mp[i - 1][1] == 'R' && mp[i][1] == 'R') {
                dp[i][1] = max(dp[i][1], dp[i - 1][1] + 1);
            }
        }
        { // 下 -> 上右
            if (mp[i - 1][2] == 'R' && mp[i - 1][1] == 'R' && mp[i][1] == 'R') {
                dp[i][1] = max(dp[i][1], dp[i - 1][2] + 2);
            }
        }
        { // 下 -> 右
            if (mp[i - 1][2] == 'R' && mp[i][2] == 'R') {
                dp[i][2] = max(dp[i][2], dp[i - 1][2] + 1);
            }
        }
    }
    int ans = 0;
    for (int i = 1 ; i <= n ; i++) {
        if (mp[i][1] == 'R' && mp[i][2] == 'R') {
            dp[i][1]++;
            dp[i][2]++;
        }
        ans = max(ans, max(dp[i][1], dp[i][2]) - 1);
    }
    cout << ans << "\n";
    return 0;
}

D Taking Candies

题意

\(A,B\) 两人竞拍 \(n\) 盒糖果，第 \(i\) 盒糖果有 \(a_i\) 颗糖

\(n\) 次竞价，每次竞价的过程是：

假设一开始 \(A,B\) 分别有 \(p,q\) 个硬币。
\(A\) 先出价 \(0\le v_0\le p\)
然后 \(B\) 出价 \(v_0< v_1\le q\) 或弃权
然后 \(A\) 出价 \(v_1< v_2\le p\) 或弃权
一直到有人弃权，假设最后出价是 \(v_m\)，则出价的人将 \(v_m\) 个硬币给对方，并且出价的人可以随意拿走一盒糖果。

一开始 \(A,B\) 分别有 \(x,y\) 个硬币，问最优策略下 \(A\) 最多拿多少糖果。

解题思路

很容易知道，拿糖果的顺序是按照数量递减的（先拿多的）。

然后我们可以发现，他们两人轮流竞价，肯定能存在每人只出一次价格的最优策略。

硬币的总和不变。

设总共有 \(s=x+y\) 枚硬币。

定义 \(f_{i,t}\) 为倒数第 \(i\) 轮 \(A\) 取得 \(t\) 个糖果所需的最少硬币，可以知道 \(f_{0,0}=0\)。

假设 \(A\) 有 \(x\) 个硬币，\(B\) 有 \(y\) 个硬币，这一轮的糖果数量为 \(w\)。

若 \(A\) 想得到这个糖果，那么他出价的最大值为 \(x-f_{i-1,t-w}\)，

那么如果 \(B\) 要拿到这个糖果，要出价 \(x-f_{i-1,t-w}+1\)，

如果 \(x+x-f_{i-1,t-w}+1\ge f_{i-1,t}\)，说明 \(A\) 之后可以拿到 \(t\) 个糖果，

得 \(f_{i,t}=\lfloor\dfrac{f_{i-1,t-w},f_{i-1,t}}{2}\rfloor\)

然后我们就得到了转移方程，我们发现糖果的数量很大，不能直接这么写。

然后我们看到 \(f_{i,t}\) 的取值为 \([0,x+y]\)，然后我们可以发现 \(f_{i,t}\) 是关于 \(t\) 单调的，

也就是说 \(t\) 相同时， \(f_{i,t}\) 递增。

所以我们可以用 vector 套 pair 存一个区间来维护单调性。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
const i64 INF = 1e12;
int a[100005];
int main() {
    int n, x, y;
    cin >> n >> x >> y;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    int s = x + y;
    vector<array<i64, 2>> f;
    f.push_back({0, 0}); // 初始状态
    f.push_back({s + 1, INF}); // 无穷状态(不可到达)
    for (int i = 1 ; i <= n ; i++) {
        vector<array<i64, 2>> g;
        auto add = [&](i64 cost, i64 val) {
            if (g.empty() || g.back()[0] < cost) {
                g.push_back({cost, val});
                return;
            }
            g.back()[1] = val;
        };
        int L = 0, R = 0;
        int len = f.size();
        while (L < len - 1 || R < len - 1) {
            int cost = (f[L][0] + f[R][0]) / 2;
            if (f[L][1] < f[R][1] + a[i]) { // 差小于 w, 不可以拿到 w
                add(cost, f[L][1]);
                L++;
            } else { // 差大于等于 w, 可以拿到 w
                add(cost, f[R][1] + a[i]);
                R++;
            }
        }
        g.push_back({s + 1, INF}); // 无穷状态(不可到达)
        f.swap(g);
    }
    i64 ans = 0;
    for (auto &[cost, val] : f) {
        if (cost <= x) {
            ans = val;
        }
    }
    cout << ans;
    return 0;
}

E GCD VS XOR

题意

给出一个正整数 \(x\)，和式子 \(\gcd(x,y)=x\oplus y\) 的 \(y\) 且 \(0\le y<x\)。

输出一个满足条件的 \(y\)。(不存在输出 \(-1\))

解题思路

看到异或运算，首先就要考虑二进制。

通过相邻的数互质和相邻的数异或为 \(1\)，可以写出 \(\gcd(x,x+1)=x\oplus y=1\)，

那么我们可以知道 \(\gcd(x*2^i,(x+1)*2^i)=2^i\)，

然后可以发现 \((x*2^i)\oplus((x+1)*2^i)=2^i\)，

乘上 \(2^i\) 相当于二进制往左移了 \(i\) 位，

所以我们可以找到 \(x\) 二进制为 \(1\) 的最低位将其置 \(0\)，

因为 \(1\) 的最低位的低位全是 \(0\)，

那么就构造出 \(x*2^i\) 和 \((x+1)*2^i\) 了，

如何找二进制为 \(1\) 的最低位，使用 \(lowbit\) 的原理 \(x\&-x\) 即可解决。

综述，答案为 \(ans=x-(x\&-x)\)，

因为 \(ans>0\)，需要特判当 \(ans=0\) 时，\(ans=-1\)。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
void solve() {
    i64 x;
    cin >> x;
    x = x & -x;
    if (x == 0) {
        x = -1;
    }
    cout << x << "\n";
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

G The Set of Squares

题意

定义一个多重集是好的，当且仅当，这个多重集内元素的乘积是一个\(x^2\)，\(x\in N\)，集合的权值为 \(x\)。

给你一个多重集，问它的所有子集中所有好集的权值和。答案对 \(1e9+7\) 取模。

解题思路

我们可以知道权值是 \(\le1000\) 的，我们可以发现，只有 \(\le\sqrt{1000}\) 的质数会在一个数中出现多次。

然后我们可以知道这种质数只有 \({2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31}\)，一共 \(11\) 个，

我们可以对这些质数状压，即 \(2^{11}\) 种状态。

这里我们想到背包，对于每个 \(>\sqrt{1000}\) 质数进行分组，那么我们可以想到如果当前质数是 \(>\sqrt{1000}\) 的，

那么只有相同组别的会产生贡献。

所以直接状压+分组背包即可解决。时间复杂度 \(o(n*2^{11}*11)\)

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int a[1005];
int prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
const i64 P = 1000000007;
vector<array<i64, 2>> v[1005];
array<i64, 1 << 12> f;
int main() {
    int n;
    cin >> n;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
    }
    for (int i = 1 ; i <= n ; i++) {
        int mask = 0;
        i64 val = 1;
        int x = a[i];
        for (int j = 0 ; j < 11 ; j++) {
            int p = prime[j];
            while (x % p == 0) {
                x /= p;
                if (mask >> j & 1) {
                    val = val * p % P;
                }
                mask ^= 1 << j;
            }
        }
        v[x].push_back({mask, val});
    }
    f[0] = 1;
    for (auto &[mask, val] : v[1]) {
        auto g = f;
        for (int j = 0 ; j < (1 << 11) ; j++) {
            int temp = j ^ mask;
            i64 res = f[j] * val % P;
            int both = j & mask;
            for (int k = 0 ; k < 11 ; k++) {
                if (both >> k & 1) {
                    res = res * prime[k] % P;
                }
            }
            g[temp] = (g[temp] + res) % P;
        }
        f = g;
    }
    for (int i = 2 ; i <= 1000 ; i++) {
        if (i * i <= 1000) {
            continue;
        }
        for (auto &[mask, val] : v[i]) {
            auto g = f;
            mask |= 1 << 11;
            for (int j = 0 ; j < (1 << 12) ; j++) {
                int temp = j ^ mask;
                i64 res = f[j] * val % P;
                int both = j & mask;
                for (int k = 0 ; k < 11 ; k++) {
                    if (both >> k & 1) {
                        res = res * prime[k] % P;
                    }
                }
                if (both >> 11 & 1) {
                    res *= i;
                }
                g[temp] = (g[temp] + res) % P;
            }
            f = g;
        }
        for (int j = 1 << 11 ; j < (1 << 12) ; j++) {
            f[j] = 0;
        }
    }
    cout << (f[0] + P - 1) % P;
    return 0;
}

H Instructions Substring

题意

给出一个仅含有 'W', 'A', 'S', 'D' 的字符串，和一个点 \((x,y)\)。

有一个平面直角坐标系，起点为 \((0,0)\)。

'W'，'A'，'S'，'D' 分别代表往上，下，左，右走一格。

问按顺序执行操作能经过点 \((x,y)\) 的子串有多少种。

解题思路

首先可以知道，如果目标点为 \((0,0)\)

那么一开始就经过了这个点，所以任意子串都满足要求，

\(ans=\frac{n*(n+1)}{2}\)。

然后我们要知道，左端点相同的子串，右端点大的一定经过右端点小的路径中的所有点。

所以我们可以考虑枚举左端点，

如果我们知道了左端点所以我们可以考虑枚举左端点，

当执行一段操作后恰好到达了目标点，那么再往后面加任何操作都是满足要求的。

所以我们可以枚举左端点，对于每个左端点都求出一个满足要求的最小右端点，

通过减法求出对应左端点满足的子串数量即可不重不漏的统计答案。

对于如何快速的找到右端点，我们可以对 \(x\) 和 \(y\) 方向进行后缀和，

有 \(sum_{X,L}-sum_{X,R-1}=x\) 和 \(sum_{Y,L}-sum_{Y,R-1}=y\)

我们只需要开一个 map 存 \({X,Y}\) 的最小下标就好了。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
array<int, 2> a[200005];
array<int, 2> sum[200005];
map<array<int, 2>, int> st;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, x, y;
    cin >> n >> x >> y;
    string str;
    cin >> str;
    str = " " + str;
    if (x == 0 && y == 0) {
        cout << 1LL * (1 + n) * n / 2 << "\n";
        return 0;
    }
    for (int i = 1 ; i <= n ; i++) {
        if (str[i] == 'A') {
            a[i][0] = -1;
        }
        if (str[i] == 'D') {
            a[i][0] = 1;
        }
        if (str[i] == 'W') {
            a[i][1] = 1;
        }
        if (str[i] == 'S') {
            a[i][1] = -1;
        }
    }
    st[{0, 0}] = n + 1;
    for (int i = n ; i >= 1 ; i--) {
        sum[i][0] = a[i][0] + sum[i + 1][0];
        sum[i][1] = a[i][1] + sum[i + 1][1];
    }
    i64 ans = 0;
    for (int i = n ; i >= 1 ; i--) {
        int X = sum[i][0] - x;
        int Y = sum[i][1] - y;
        if (st.count({X, Y})) {
            ans += n + 2 - st[{X, Y}];
        }
        int idx = i;
        if (st.count({sum[i][0], sum[i][1]})) {
            idx = min(idx, st[{sum[i][0], sum[i][1]}]);
        }
        st[{sum[i][0], sum[i][1]}] = idx;
    }
    cout << ans << "\n";
    return 0;
}

I Red Playing Cards

题意

有 \(2n\) 个数，\(1\) 到 \(n\) 各有两张，

你可以进行任意次操作，每次操作你可以选择两张相同的数 \(x\)，

假设下标分别为 \(L,R\)，把下标在区间 \([L,R]\) 的数都删掉，那么你能获得价值 \(x*(R-L+1)\)。

问最大可能获得的价值。

解题思路

我们可以发现，删除的区间一定不能交叉，而且删除的区间前后端点的数一定相同。

那么我们就只要考虑这个区间内的区间，因为可能有嵌套，所以用 dfs 枚举所有区间，

使用 dp 来计算这个区间的最大权值，从而处理出所有区间的贡献。

最后进行一次 dp 递推出最大权值。

解题代码

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int a[6005];
int dp[6005];
int pos[6005][2];
int temp[6005][6005];
int dfs(int x) {
    if (dp[x] != 0) {
        return dp[x];
    }
    int L = pos[x][0], R = pos[x][1];
    temp[x][L] = x;
    for (int i = L + 1 ; i <= R ; i++) {
        temp[x][i] = max(temp[x][i], temp[x][i - 1] + x);
        int QL = pos[a[i]][0], QR = pos[a[i]][1];
        if (i == QL && QR < R) {
            temp[x][QR] = max(temp[x][QR], temp[x][i - 1] + dfs(a[i]));
        }
    }
    return dp[x] = temp[x][R];
}
int ans[6005];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1 ; i <= 2 * n ; i++) {
        cin >> a[i];
        if (pos[a[i]][0]) {
            pos[a[i]][1] = i;
        } else {
            pos[a[i]][0] = i;
        }
    }
    for (int i = 1 ; i <= n ; i++) {
        dfs(i);
    }
    for (int i = 1 ; i <= 2 * n ; i++) {
        ans[i] = max(ans[i], ans[i - 1]);
        int L = pos[a[i]][0], R = pos[a[i]][1];
        if (i == L) {
            ans[R] = max(ans[R], ans[i - 1] + dp[a[i]]);
        }
    }
    cout << ans[2 * n] << "\n";
    return 0;
}

J Involutions

题意

定义 \(involution\) 为集合上有映射 \(f:A\to A\) 且 \(f(f(x))=A\)。

定义 \(FP(f)=\mid{x\in A\mid f(x)=x}\mid\)

定义 \(w(f)=a^{FP(f)}\)

问 \(\{1,2,3,…,n\}\) 上所有 \(involution\) 的权值和，答案对 \(998244353\) 取模。

解题思路

令 \(g(n)\) 为 \(\{1,2,3,…,n\}\)上所有 \(involution\) 的权值和。

易知： \(g(0)=1\) 和 \(g(1)=a\) 。

当我们现在有 \(n-1\) 个数，我们新增一个数 \(x\)，使 \(f(x)=x\)，这样也有 \(f(f(x))=x\)，此时 \(FP\) 多了 \(1\)，所以贡献了 \(a*g(n-1)\)，

当我们现在有 \(n-2\) 个数，我们新增一个数 \(x\)，我们可以选择已有的任意一个数 \(y\)，使 \(f(x)=y,f(y)=x\)，这样也有 \(f(f(x))=x,f(f(y))=y\)，此时 \(FP\) 不变，在 \(g(n-2)\) 的基础上，任意选一个数出来和 \(x\) 匹配，所以贡献 \(g(n-2)*(n-1)\)。

所以我们得到式子 \(g(n)=a*g(n-1)+(n-1)*g(n-2)\)

这里使用整式递推模版即可。

解题代码

代码

C++
{ 多项式基础模版 }
{ 整式递推模版 }
int main() {
    i64 n, a;
    cin >> n >> a;
    if (n <= 5) {
        vector<int> ans(n + 1);
        ans[0] = 1; ans[1] = a;
        for (int i = 2 ; i <= n ; i++) {
            ans[i] = (a * ans[i - 1] + 1LL * ans[i - 2] * (i - 1)) % P;
        }
        cout << ans[n] << "\n";
        return 0;
    } else {
        recursive::init();
        vector<Int> f{1, a};
        vector<vector<Int>> p{
            {P - 1, 0},
            {a, 0},
            {P - 1, 1}
        };
        cout << recursive::recursive(n, f, p) << "\n";
    }
    return 0;
}