CF1916 Goodbye2023 H1H2 题解

· · 题解

前言

这场比赛打得异常痛苦。 虽然场上 H1H2 会做，但是考场上太急了导致脑抽，然后就爆掉了。。。

题意

给定 n，p，k。要求： 求有多少个 n\times n 的在 \bmod p 意义下定义的矩阵，使得其秩为 r。 将 r 从 0 到 k 分别输出答案，对 998244353 取模。

数据范围：n \le 5\times10^{18}，k \le 5\times 10^5，0 \le p < 998244353。

题解

容易想到 dp：f_{i,r} 表示考虑前 i 行的矩阵，秩为 r 的数量。 显然有

f_{i,r} = f_{i - 1,r} \times p^r + f_{i - 1, r - 1} \times (p^n - p^{r - 1})

具体而言，分两种情况：

  1. 当前秩不增加，那么这行一定是前面的行向量的组合，因为前面的秩 r，所以有 2^r 种方法。
  2. 当前秩增加，那么这行一定不是前面的行向量的组合，因为前面的秩为 r - 1，所以有 p^n - p^{r - 1} 中选择方法。

那么这样就得到如上转移，最终答案是 f_{n,0},\cdots,f_{n,k}。

考虑如何快速求解 f 数组。考虑将 f 数组画在一个二维平面上，等价于：

每次可以从 (i,r) 走到 (i+1,r)（称为平走），或者从 (i,r) 走到 (i + 1, r + 1)，每次行走带着一定的贡献。

可以发现第 2 种转移一定只有 r 个，且对答案的贡献是确定的，即：

f_{i,r} = g_{r,i-r} \times \Pi_{j=1}^r (p^n - p^{j - 1})

其中，走到 f_{i,r} 需要进行 i - r 次第 1 种转移，那么 g_{i,r} 的意义就明确了。

所以 g_{i,r} 就是在 1 到 i 层种进行若干次（可以为 0）平走，使得总平走的次数恰好为 r 的总贡献，在第 j 层平走的贡献是 p^j。 由于有恰好走 r 步，所以考虑生成函数：G_i(x) = \sum_{r\ge0} f_{i,r}x^r，

从而可以写出 G_i(x) = \sum_{j=0}^i \sum_{l\geq0}(p^jx)^l=\sum_{j=0}^i\tfrac{1}{1-p^jx}，考虑：

G_i(x) = \sum_{j=0}^i\dfrac{1}{1-p^jx} G_i(px) = \sum_{j=0}^i\dfrac{1}{1-p^j(px)}=\sum_{j=0}^i\dfrac{1}{1-p^{j+1}x}

所以有

(1 - x)G_i(x) = (1 - p^{i+1}x)G_i(px)

对比两边 r 次方系数的：

g_{i,r}- g_{i,r-1}=p^r\times g_{i,r}-p^{i+1}\times p^{r-1} \times g_{i,r-1}

所以就可以得到递推公式：

g_{i,r}=\dfrac{p^{i+r}-1}{p^r-1}\times g_{i,r-1}

所以就得到了通项公式：

g_{i,0}=1,g_{i,r}=\Pi_{j=1}^r\dfrac{p^{i+j}-1}{p^j-1}

从而得到了快速求解 f 的方法：

f_{n,r} = \Pi_{j=1}^{n-r}\dfrac{p^{r+j}-1}{p^j-1} \times \Pi_{j=1}^r (p^n - p^{j - 1})

考虑将 r 从小到大计算，则后者可以直接算，前者考虑分子分母互相抵消后再计算。

然后这样就可以直接过 H1H2 了。

#include <bits/stdc++.h>
using namespace std;
#define int long long

int rd() {
    int x = 0, f = 1;
    char ch = getchar();
    while (!('0' <= ch && ch <= '9')) {
        if (ch == '-') f = -1; ch = getchar();
    }
    while ('0' <= ch && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();
    }
    return x * f;
}

void wr(int x) {
    if (x < 0) putchar('-'), x = -x;
    if (x >= 10) wr(x / 10); putchar(x % 10 + '0');
}

const int N = 5e5 + 10;
const int mod = 998244353;

int ans[N];

int add (int x) {
    if (x >= mod) x -= mod; else if (x < 0) x += mod;
    return x;
}

int ksm (int x, int y = mod - 2) {
    int res = 1; x = add(x);
    while (y) {
//      cout << y << " " << res << endl;
        if (y & 1) res = 1ll * res * x % mod;
        x = 1ll * x * x % mod; y >>= 1;
    } return res;
}

signed main() {
    int n, p, k; n = rd(); p = rd(); k = rd();
    int res1 = 1, res2 = 1;
    for (int r = 0; r <= min(n,k); ++r) {
        ans[r] = 1ll * res1 * res2 % mod;
        res1 = 1ll * res1 * add(ksm(p, n) - ksm(p, r)) % mod;
        res2 = 1ll * res2 * ksm(ksm(p, r + 1) - 1) % mod * add(ksm(p, n - r) - 1) % mod;
    }
    for (int r = 0; r <= k; ++r) printf ("%d ", ans[r]);
    return 0;
}

话说，上面最后的式子是可以用找规律的？不清楚了。