[洛谷题解] CF547A Mike and Frog

发布于 2019-10-23  1.36k 次阅读

题目链接：CF547A Mike and Frog

题目大意

你有两个数 H_1、H_2。每次操作，你可以将 H_1 变成 (H_1 \cdot x_1 + y_1)\ mod\ M，H_2 变成 (H_2 \cdot x_2 + y_2)\ mod\ M （两个变换会在一次操作时同时进行）。

问，你至少需要进行多少次操作，才能使得 H_1 = A_1 和 H_2 = A_2 同时满足。

数据范围：H_1,x_1,y_1 ，H_2,x_2,y_2 < M ，2 \leq M \leq 10^6

解题思路

注意到本题 M 只有 10^6，我么可以对于 H_1 和 H_2 分别暴力模拟。

对于一个数 a，如果不断进行操作，其变化规律应当如下：

a → b → (c → d → e → f) → (c → d → e → f) → ...

感性理解一下，我们发现这个数进行一定次数操作后一定会进入一个循环。

我们称这个数达到第一个 c （如上面的描述）之后就算进入了循环，到达第二个 c 时算“发生循环”。那么，一个数的变化规律可以这么描述：

  • 对于任意一个数，其变换 0 次或若干次就会进入一个长度大于 0 （废话），且小于等于 M 的循环。

比如，上面的描述中，a 在变换两次后就进入了一个长度为 4 的循环。

我们用 a^k 表示数 a 操作 k 次后的结果，用 rd_a 表示 a 进入循环前的变换次数，用 r_a 表示 a 进入的循环的长度。

对于 H_1，我们先暴力求出一个最小的 cnt_{H_1}（其实这样表示不准确，但是为了和rd、r的表达方式对等所以这么写），使得 H_1^{cnt_{H_1}} = A_1。我们还可以暴力求出 rd_{H_1} 和 r_{H_1}。

然后我们很容易知道 H_1^x = A_1 的条件。

  • 如果 cnt_{H_1} < rd_{H_1}，则当且仅当正整数 k 满足 k = cnt_{H_1} 时，有 H_1^k = A_1
  • 否则，当且仅当正整数 k 同时满足以下条件时，有 H_1^k = A_1
    • k \geq rd_{H_1} （显然）
    • (k - rd_{H_1})\ mod\ r_{H_1} = (cnt_{H_1} - rd_{H_1}) （即，经过若干次循环以后会回到我们需要的位置）

然后我们对于 H_2 也这样计算。随后我们分类讨论如何求得答案ans。

  • 如果两个数的 cnt 均小于 rd，那么，ans 必须满足 ans = cnt_{H_1} 和 ans = cnt_{H_2}。那么，当且仅当 cnt_{H_1} = cnt_{H_2} 时有解，解是 cnt_{H_1}。
  • 如果只有一个数的 cnt 小于 rd，不妨令 cnt_{H_1} < rd_{H_1}。那么，必定有 ans = cnt_{H_1}。那么，当且仅当 cnt_{H_1} \geq rd_{H_2} 且 (cnt_{H_1} - rd_{H_2})\ mod\ r_{H_2} = (cnt_{H_2} - rd_{H_2}) 时有解，解是 cnt_{H_1}。
  • 如果没有一个数的 cnt 小于 rd，那么，ans 必须满足：
    • ans \geq rd_{H_1} \texttt{\color{grey}condition 1}
    • ans \geq rd_{H_2} \texttt{\color{grey}condition 2}
    • (ans - rd_{H_1})\ mod\ r_{H_1} = (cnt_{H_1} - rd_{H_1}) \texttt{\color{grey}condition 3}
    • (ans - rd_{H_2})\ mod\ r_{H_2} = (cnt_{H_2} - rd_{H_2}) \texttt{\color{grey}condition 4}

那么对于第三种情况，我们定义变量 p，并赋值为满足条件1和3的最小值。很显然，此时 p = cnt_{H_1}。

随后，我们不停地将 p 的值增加 r_{H_1} （可知这样不会破坏条件1和3），直到其满足条件2。由于 rd_{H_2} 最大只能为 M-1，所以不会超时。此时的 p 已经同时满足条件1，2和3。

最后我们再将 p 的值不停增加 r_{H_1} （可知这样不会破坏条件1，2，3），直到 p 满足条件4（此时答案为 p），或者已经增加了超过 M 次（此时无解）。

综合所有情况，就是正解了。

代码

注意千万不要把 y1 定义成全局变量！如果评测机编译器版本较老，这会和 math.h 冲突，造成错误。

// status: [Accepted]
// oj:     [%uContest]

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

// 不开 long long 见祖宗
typedef long long ll;
#define int ll

// 题目中的 M
int mod1;

// 让 h 每次以 h = (h * x + y) % mod1 的形式变换，返回变换到 a 所需的最少步骤数。
// 如果无法变换到 a，返回-1
// * flag: 是否允许在 h==a 时返回0
int findNext(int h,int a,int x,int y,bool flag = false) {
    int cnt = 0;
    if(flag && h==a) return 0;
    do {
        cnt++;
        h = (h * x + y) % mod1;
        // 如果变换超过 M 次还没有找到答案，那么此时肯定已经“发生循环”，不可能还会找到答案。
        if(cnt > mod1) {
            return -1;
        }
    } while(h != a);
    return cnt;
}

int st[1000000];
int st_t = 0;
// 让 h 每次以 h = (h * x + y) % mod1 的形式变换，返回 h 初次“进入循环”时变成的数。
int findCyclicNode(int h,int x,int y) {
    // 可以直接用数组统计是否出现。此处使用一个计数量(st_t)，可以避免清空数组的麻烦
    ++st_t;
    // 此处要先记录访问 h 一次，否则如果 h 本身就在循环内，会出现问题。
    st[h] = st_t;
    // 由于一个数不断变换必定会出现循环，因此while(1)即可。
    while(1) {
        h = (h * x + y) % mod1;
        // 第一个出现超过 1 次的值，一定是初次“进入循环”时的值
        if(st[h] == st_t) return h;
        st[h] = st_t;
    }
}

// 除法上取整（避免double精度问题）
// * 这份代码中没有用到此函数
int divCeil(int x,int y) {
    return x/y + int(bool(x%y));
}

signed main() {
#ifdef OFFLINE_JUDGE
    freopen("water.in","r",stdin);
    freopen("water.out","w",stdout);
#endif

    // 不要将 y1 作为全局变量，否则要换个名字。
    int h1,a1,x1,y1;
    int h2,a2,x2,y2;

    ios::sync_with_stdio(false);
    cin>>mod1>>h1>>a1>>x1>>y1>>h2>>a2>>x2>>y2;

    // 求cnt_{H_1}
    int cnt1 = findNext(h1,a1,x1,y1);
    int cnt2 = findNext(h2,a2,x2,y2);

    // H_1 和 H_2 有一个无法到达 A_1 或 A_2。无解。
    if(cnt1 == -1 || cnt2 == -1) {
        cout<<-1<<endl;
        exit(0);
    }

    // 先寻找初次进入循环时到达的数字
    int p1 = findCyclicNode(h1,x1,y1);
    int p2 = findCyclicNode(h2,x2,y2);

    // 再求循环长度
    int r1 = findNext(p1,p1,x1,y1);
    int r2 = findNext(p2,p2,x2,y2);

    // 然后求初次进入循环之前的步骤数
    int rd1 = findNext(h1,p1,x1,y1,true);
    int rd2 = findNext(h2,p2,x2,y2,true);

    // cnt - rd 在解法中被频繁使用，创建变量以图方便。
    int d1 = cnt1 - rd1;
    int d2 = cnt2 - rd2;

    // 忘记删除的调试信息（在一般的平台下，使用cerr输出调试信息可避免一部分的“不删调试见祖宗”）
    cerr<<"1: "<<r1<<' '<<rd1<<' '<<d1<<endl;
    cerr<<"2: "<<r2<<' '<<rd2<<' '<<d2<<endl;

    // 如果两个数都有 cnt < rd （即 cnt - rd < 0）
    if(d1 < 0 && d2 < 0) {
        if(cnt1 == cnt2) {
            cout<<cnt1<<endl;
        }
        else {
            cout<<-1<<endl;
        }
        exit(0);
    }
    // 如果只有一个数
    else if(d1 < 0) {
        if(cnt1 - rd2 >= 0 && (cnt1 - rd2) % r2 == d2) {
            cout<<cnt1<<endl;
        }
        else {
            cout<<-1<<endl;
        }
        exit(0);
    } else if(d2 < 0) {
        if(cnt2 - rd1 >= 0 && (cnt2 - rd1) % r1 == d1) {
            cout<<cnt2<<endl;
        }
        else {
            cout<<-1<<endl;
        }
        exit(0);
    }

    // 如果没有数满足 cnt < rd
    // 先使p满足条件1和3
    int p = rd1 + d1;
    // 然后满足2
    while(p < rd2) p += r1;
    // 最后满足4
    for(int i=1;i<=r2+1;i++,p+=r1) {
        if((p-rd2) % r2 == d2) {
            cout<<p<<endl;
            exit(0);
        }
    }

    // 无解
    cout<<-1<<endl;
}

评测记录：R25577582

赏

undefined