考场里oier出来问保出题人还是保监考

_ACGODs_ · 2025-08-11 13:55:58 · 题解

本题解已死

本题解已死

本题解已死

本题解已死

本题解已死

本题解已死

P13460 题解

本题解使用了 2025 年 7 月渲染更新以优化视觉效果。

思路

容易发现，三角形的三个点的 x 坐标之和和 y 坐标之和都要为 3 的倍数时，中心点才能满足条件。
也就是：

:::align{center} 且 :::

下文中“条件”均指以上同余条件。
我们只需要枚举三个点，满足条件就好了。
吗？

代码优化

枚举的思路是正确的，但效率太低，只能通过小数据集。
可以发现，每个点可以分为 9 类，分别对应 x_i ,y_i \bmod 3 的那些情况。
最后，只需要把满足条件的情况组合（也就是这些情况的 x 值和 y 值之和 \equiv 0 \pmod 3）乘在一起，再去个重，就好了。

自认为不清楚的地方，请配合代码进行理解。 :::info[小优化] 可以先枚举前两个点的 x ,y \bmod 3 的值 ，第三个点可以通过公式求出而不是枚举再判断。
本题解代码不使用这个优化。 :::

代码

//注释会引用思路和优化部分的内容。
#include <bits/stdc++.h>
using namespace std;
//初音未来和多人保持暧昧，我就是受害者之一[doge]
#define int long long
int t, n, a, b, c, d, x[100010], y[100010], m;
int xymd[5][5];
signed main() {
    cin >> t;
    for (int cas = 1; cas <= t; cas++) {
        int ans = 0;
        cin >> n >> a >> b >> c >> d >> x[1] >> y[1] >> m;
        memset(xymd, 0x00, sizeof xymd);//咱班有个同学叫hao*****uo，他没初始化而在去年CSP-T2中获得30分の好成绩。
        xymd[x[1] % 3][y[1] % 3]++;//可以发现，每个点可以分为 9 类，分别对应 xi,yi mod 3 那些情况
        for (int i = 2; i <= n; i++) {
            x[i] = (a * x[i - 1] + b) % m;
            y[i] = (c * y[i - 1] + d) % m;
            xymd[x[i] % 3][y[i] % 3]++;//同上
        }
        ans = 0;
        for (int i = 0; i <= 2; i++) {
            for (int j = 0; j <= 2; j++) {
                for (int k = 0; k <= 2; k++) {
                    for (int l = 0; l <= 2; l++) {
                        for (int p = 0; p <= 2; p++) {
                            for (int q = 0; q <= 2; q++) {
                                //枚举情况
                                if ((i + k + p) % 3 == 0 && (j + l + q) % 3 == 0) {//最后，只需要把满足条件的情况组合乘在一起
                                    int cnt1 = xymd[i][j];
                                    int cnt2 = xymd[k][l];
                                    int cnt3 = xymd[p][q];
                                    //不要直接在变量上面减。要么这三个变量作备份，要么这三个变量用来减。
                                    if (i == k && j == l) cnt2--;
                                    if (i == p && j == q) cnt3--;
                                    if (k == p && l == q) cnt3--;
                                    //再去个重：
                                    //判断重复的情况。
                                    //先来后到，后面重复当然去后面的（当然全都去前面的也可以，但是不能一下去前面一下去后面）
                                    if (cnt1 > 0 && cnt2 > 0 && cnt3 > 0) ans += cnt1 * cnt2 * cnt3;
                                    //防止负数。如果去重去出负数来了那么说明本来就没有那么多可去。
                                }
                            }
                        }
                    }
                }
            }
        }
        cout << "Case #" << cas << ": " << ans / 6 /*还是有重复的，例如 A B C 和 C B A 是一种东西，而被算了两(六)次。*/<< endl;
    }
    return 0;
}