21年1月30日 模拟赛

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

A 猫哭了，你哭了吗？

题目

原题 CF1030G

给出长为 \(n\) 的均为质数的数列 \(p_1\dots p_n\)，由这个数列可以生成的数列 \(f\) 满足：\(f_i^{(0)}=x_i\)，\(f_i^{(k)}=(a_if_i^{(k-1)}+b_i)\bmod p_i\)，其中 \(a_i,b_i,x_i\) 是你选定的 \([0,p_i)\) 范围的数。求可以生成的不同数列的个数最大值。

\(n\le 2\times 10^5\)，\(p_i\le 2\times 10^6\)。

我确实哭了。

对于某一个 \(i\)，设 \(A=a_i,B=b_i,X=x_i,P=p_i\)，那么 \[ f_i\equiv Af_{i-1}+B\pmod P \] 我们显然啊不猜到 \(f_i\) 的变化轨迹是个 \(\rho\) 型环。

设每个 \(\rho\) 型环柄长 \(d_i\)，圆环周长 \(l_i\)，合并这些环就是 \(\max d_i+\operatorname{lcm}l_i\)。

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

已知 \(f_0=X\)，所以 \(\displaystyle f_i\equiv A^iX+\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)\Big(X+\frac{B}{A-1}\Big)\\ &\equiv 0 \end{aligned} \]

其中 \(n>m\ge0\)。这几个部分都考虑一下。

所以可以考虑对 \(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)\Big(X+\frac{B}{A-1}\Big)\equiv0\)。

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

以上几个情况可以定义为选择 \(1,2,3\)，我们要对每个 \(p_i\) 分配选择，使最大化 \(\max d_i+\operatorname{lcm}l_i\)。

由于 \(d_i\le1\)，先考虑 \(\operatorname{lcm}l_i\)。把 \(p_i\) 倒序排序，设 \(s\) 为当前处理过的 \(l_i\) 的 \(\operatorname{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=3g_{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)\bmod p\)。

\(1\le T\le 1000\)，\(1\le n\le10^9\)，\(1\le k\le 100\)，\(0\le a,b<p\)。

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

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

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

C 寿司晚宴

题目

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

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

\(m\le n\le 10^5\)。

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

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

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

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