21年1月30日 模拟赛

数论 + 斐波那契循环节 + 计数。

A 猫哭了，你哭了吗？

给出长为 $n$ 的均为质数的数列 $p_{1} \dots p_{n}$ ，由这个数列可以生成的数列 $f$ 满足： $f_{i}^{(0)} = x_{i}$ ， $f_{i}^{(k)} = (a_{i} f_{i}^{(k - 1)} + b_{i}) mod p_{i}$ ，其中 $a_{i}, b_{i}, x_{i}$ 是你选定的 $[0, p_{i})$ 范围的数。求可以生成的不同数列的个数最大值。

$n \leq 2 \times 10^{5}$ ， $p_{i} \leq 2 \times 10^{6}$ 。

~~我确实哭了。~~

对于某一个 $i$ ，设 $A = a_{i}, B = b_{i}, X = x_{i}, P = p_{i}$ ，那么 $f_{i} \equiv A f_{i - 1} + B (\mod P)$ 我们显然啊不猜到 $f_{i}$ 的变化轨迹是个 $ρ$ 型环。

设每个 $ρ$ 型环柄长 $d_{i}$ ，圆环周长 $l_{i}$ ，合并这些环就是 $max d_{i} + lcm l_{i}$ 。

套路地，联立 $(f_{i} + k) \equiv A (f_{i - 1} + k) (\mod P)$ ，解得 $k \equiv \frac{B}{A - 1}$ 。

已知 $f_{0} = X$ ，所以 $f_{i} \equiv A^{i} X + \frac{(A^{i} - 1) B}{A - 1}$ 。 $\begin{aligned} f_{n} - f_{m} & \equiv (A^{n} - A^{m}) X + \frac{(A^{n} - A_{m}) B}{A - 1} \\ \equiv A^{m} (A^{n - m} - 1) (X + \frac{B}{A - 1}) \\ \equiv 0 \end{aligned}$

其中 $n > m \geq 0$ 。这几个部分都考虑一下。

所以可以考虑对 $a_{i}$ 分类讨论：

$a_{i} = 0$ ，显然 $d_{i} = 1$ ， $l_{i} = 0$ ；
$a_{i} = 1$ ，直接进入环， $d_{i} = 0$ ， $l_{i} = p_{i}$ ；
$a_{i} > 1$ ，此时 $d_{i} = 0$ ，可以得到 $(A^{n} - 1) (X + \frac{B}{A - 1}) \equiv 0$ 。

$(X + \frac{B}{A - 1}) \equiv 0$ 时 $l = 0$ ，这是不优的，那么 $A^{n} - 1 \equiv 0$ ，费马小定理得到 $n = φ (P) = P - 1$ 。即 $l = p_{i} - 1$ 。

以上几个情况可以定义为选择 $1, 2, 3$ ，我们要对每个 $p_{i}$ 分配选择，使最大化 $max d_{i} + lcm l_{i}$ 。

由于 $d_{i} \leq 1$ ，先考虑 $lcm l_{i}$ 。把 $p_{i}$ 倒序排序，设 $s$ 为当前处理过的 $l_{i}$ 的 $lcm$ ，如果 $s$ 没有包含 $p_{i}$ 这个质因子，我们肯定是尽量选选择 $2$ ；否则选选择 $3$ 。

怎么分配选择 $1$ 的这个 $d_{i} = 1$ 呢？找一个最没用的。具体地，记录 $s$ 每一个质因数的最高次幂，已经包含这个最高次幂的 $l_{i}$ 的个数。再扫一遍所有 $l_{i}$ ，如果去掉它对 $s$ 无影响，就令它为选择 $1$ 。

代码

typedef long long LL;

const int N = 2e6 + 5;
const int P = 1e9 + 7;

inline int power(int x, int y) {
    int res = 1;
    while (y) {
        if (y & 1) res = (LL)res * x % P;
        x = (LL)x * x % P, y >>= 1;
    }
    return res;
}

int n, cntp, ans;
int a[N], pri[N], ma[N], cnt[N];
bool np[N], wc[N];

inline void get_prime(int lim) {
    np[1] = true;
    for (int i = 2; i <= lim; ++i) {
        if (!np[i]) pri[++cntp] = i;
        for (int j = 1; j <= cntp && pri[j] * i <= lim; ++j) {
            np[pri[j] * i] = true;
            if (i % pri[j] == 0) break;
        }
    }
}

inline void update(int p, int c) {
    if (c > ma[p]) ma[p] = c, cnt[p] = 1;
    else if (c == ma[p]) ++cnt[p];
}

inline void deco(int x) {
    for (int i = 1; i <= cntp && pri[i] * pri[i] <= x; ++i) {
        int p = pri[i];
        if (x % p) continue;
        int c = 0;
        while (x % p == 0) x /= p, ++c;
        update(p, c);
    }
    if (x > 1) update(x, 1);
}

inline bool check(int x) {
    if (!np[x]) { // bug
        if (ma[x] == 1 && cnt[x] == 1) return false;
        return true;
    }
    for (int i = 1; i <= cntp && pri[i] * pri[i] <= x; ++i) {
        int p = pri[i];
        if (x % p) continue;
        int c = 0;
        while (x % p == 0) x /= p, ++c;
        if (ma[p] == c && cnt[p] == 1) return false;
    }
    if (x > 1 && ma[x] == 1 && cnt[x] == 1) return false; // bug
    return true;
}

inline void main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    sort(a+1, a+n+1), reverse(a+1, a+n+1);
    get_prime(a[1]);
    ans = 1;
    for (int i = 1; i <= n; ++i) {
        if (ma[a[i]]) deco(a[i] - 1), wc[i] = true;
        else update(a[i], 1);
    }
    for (int i = 1; i <= cntp; ++i) {
        if (!ma[pri[i]]) continue;
        ans = (LL)ans * power(pri[i], ma[pri[i]]) % P;
    }
    for (int i = 1; i <= n; ++i) {
        if ((wc[i] && check(a[i] - 1)) || (!wc[i] && check(a[i]))) {
            ++ans;
            break;
        }
    }
    cout << ans << '\n';
}

B 迫害

题目

已知 $g_{0} = a$ ， $g_{1} = b$ ， $g_{i} = 3 g_{i - 1} - g_{i - 2}$ ； $f (n, 0) = n$ ， $f (n, k) = f (g (n), k - 1)$ 。

给出 $a, b, n, k, p$ ，求 $f (n, k) mod p$ 。

$1 \leq T \leq 1000$ ， $1 \leq n \leq 10^{9}$ ， $1 \leq k \leq 100$ ， $0 \leq a, b < p$ 。

斐波那契循环节 + 矩阵快速幂。

考场上想写 $60$ 分，随机化找循环节 + $O (\log n)$ 快速幂 + 巨大常数，混了个 $35$ 分。

求斐波那契循环节的确定性算法及证明还没懂，先咕。

C 寿司晚宴

题目

有 $n$ 个寿司排成一排， $m$ 个人，每个人有一个喜欢的寿司，可以以某个寿司的左右侧为起点，朝向喜欢的寿司移动，直到取走并离开；若已经被其他人拿走，方向不变继续走，取走之后遇见的第一份未被取走的寿司后离开，或者直到边界。

求所有人都能取得寿司的方案数。

$m \leq n \leq 10^{5}$ 。

先接链成环，在 $1$ 和 $n$ 之间加入 $0$ 号寿司表示断点。

考虑每个人的方向和起点，排列方案数为 $2^{m} (n + 1)^{m}$ ，除以轮换数 $n + 1$ 就是圆排列方案数。

然后我们钦定每个人都能拿到寿司，显然没有人会拿的寿司有 $n - m + 1$ 个并且不再某个人的路径上，即可以放断点的方案数。

所以最后方案数为： $2^{m} (n + 1)^{m - 1} (n - m + 1)$ 代码就没必要了。

RenaMoe's Blog

21年1月30日模拟赛

A 猫哭了，你哭了吗？

B 迫害

C 寿司晚宴