P2768 珍珠项链 题解

· · 题解

Link。

题目大意

有 n 种珍珠，每种 n 颗，要组成长度为 1 \sim n 的序列，且至少需要用到 k 种不同的珍珠，问有多少种方案。

思路

这题很明显是动态规划，我们假设 f[i][j]，表示使用 j 颗珍珠，长度为 i 共有多少种方案。

则 f[i][j] = f[i - 1][j] \times j + f[i - 1][j - 1] \times (k - (j - 1))。

最终答案就是: \sum\limits_{i=1}^nf[i][k]。

所以直接动态规划即可，注意多组数据。

#include <cstdio>
#define int long long

const int N = 5e4 + 5, K = 35, Mod = 1234567891;

int n, k, T, f[N][K], ans;

signed main() {
    scanf("%lld", &T);
    while (T--) {
        scanf("%lld %lld", &n, &k);
        f[0][0] = 1, ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++)
                f[i][j] = (f[i - 1][j] * j % Mod + f[i - 1][j - 1] * (k - j + 1) % Mod) % Mod;
            ans = (ans + f[i][k]) % Mod;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

可是我们把这样一份代码交上去后，发现：Link。

这时，我发现 n \le 1000000000。

数组都开不了这么大。

这个时候就要请出我们的主角——矩阵加速(不会的戳这里)。

关于这道题，我们先看到动态规划的部分：

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++)
            f[i][j] = (f[i - 1][j] * j % Mod + f[i - 1][j - 1] * (k - j + 1) % Mod) % Mod;
        ans = (ans + f[i][k]) % Mod;
    }

由于每个长度下我们都需要更新完每种情况我们才能继续更新更新下一个长度。

所以初始矩阵一定包含 f[1][1] \sim f[1][k] 这一部分。

而我们需要统计：\sum\limits_{i=1}^nf[i][k]，所以可以再在矩阵中添加一个数表示答案。

以 k = 5 举个例子：

初始矩阵为：

\left[ \begin{matrix} f[1][1] & f[1][2] & f[1][3] & f[1][4] & f[1][5] & 0 \end{matrix} \right]

现在我们需要寻找到一个矩阵和初始矩阵相乘得到：

\left[ \begin{matrix} f[2][1] & f[2][2] & f[2][3] & f[2][4] & f[2][5] & f[1][5] \end{matrix} \right]

根据递推式，我们可以知道加速矩阵应该如下：

\left[ \begin{matrix} 1 & 4 & 0 & 0 & 0 & 0\\ 0 & 2 & 3 & 0 & 0 & 0 &\\ 0 & 0 & 3 & 2 & 0 & 0 &\\ 0 & 0 & 0 & 4 & 1 & 0 &\\ 0 & 0 & 0 & 0 & 5 & 0 &\\ 0 & 0 & 0 & 0 & 0 & 1 &\\ 0 & 0 & 0 & 0 & 0 & 1 &\\ \end{matrix} \right]

所以用初始矩阵乘加速矩阵的 n 次方即可。

最终答案为结果矩阵的最后一项。

code

#include <cstdio>
#include <cstring>
#define int long long

const int N = 1e6 + 5, K = 35, Mod = 1234567891;

int n, k, T;

struct Matrix {
    int n, m, a[K][K];
    Matrix() { memset(a, 0, sizeof(a)); }
    Matrix operator * (const Matrix &c) { // 矩阵乘法
        Matrix res;
        res.n = n, res.m = c.m;
        for (int i = 1; i <= 31; i++)
            for (int j = 1; j <= 31; j++)
                for (int k = 1; k <= 31; k++)
                    res.a[i][j] = (res.a[i][j] + a[i][k] * c.a[k][j] % Mod) % Mod;
        return res;
    }
} s, ans;

inline void qkpow(int x) { // 矩阵快速幂
    while (x) {
        if (x & 1)
            ans = ans * s;
        s = s * s;
        x >>= 1;
    }
}

signed main() {
    scanf("%lld", &T);
    while (T--) {
        scanf("%lld %lld", &n, &k);
        memset(ans.a, 0, sizeof(ans.a));
        memset(s.a, 0, sizeof(s.a)); // 每次清 0，不然会错
        ans.n = 1, ans.m = k + 1, ans.a[1][1] = k;  // f[1][1] 为 k
        s.n = k + 1, s.m = k + 1;
        for (int i = 1; i <= k; i++)
            s.a[i][i] = i, s.a[i - 1][i] = k - i + 1;
        s.a[k + 1][k + 1] = s.a[k][k + 1] = 1;  // 根据刚才推出的规律得到初始矩阵
        qkpow(n);
        printf("%lld\n", ans.a[1][k + 1]);
    }
    return 0;
}