Skip to content

11583: 【原1583】Cats

题目

题目描述

author: Blacko 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1583

Description

隔壁村的阿黑的Cat跑了, 于是Cat变成了野生Cat.

野生Cat生活在隔壁村的n * n的矩形大公园,

野生Cat有着谜一样的行进路线, 当前位于(x, y)位置的猫, 在下一个时刻为出现在(NewX, NewY), 其中:

\( NewX = (A_x x^2 + B_x x + C_x + T) \mod n\) \( NewY = (A_y y^2 + B_y y + C_y + T) \mod n\)

其中\(A_x, B_x, C_x, A_y, B_y, C_y\)为给出的一个常数. T为这只野生Cat的特征值, 在公园中的初始的野猫的特征值为0.

野生Cat有着惊人的繁殖速度. 当两只性别不一样猫咪在同一时刻出现在(x, y), 则下一时刻该位置会不可描述的出现 n * 2^(x^y) 只特征值从0n * 2^(x^y) - 1的小公猫,和n * 2^(y^x)只特征值从0n * 2^(y^x) - 1的小母猫(优先计算x^yy^x(0^0 = 1)), 当多只性别不同的只野生Cat在同一位置时, 则任意两只公猫母猫之间都会发生上述事件.

我们已知第0时刻公园的野生Cat分布情况, 那么第K时刻时公园总的有多少野生Cat呢?

出于题目难度限制, 输出的野生Cat的数量对M取模.

该题坐标从(0, 0)开始.

Input Format

第一行有两个整数n, M, K含义如上.

第二行有六个整数\(A_x, B_x, C_x, A_y, B_y, C_y\), 含义如上.

第三行有一个整数 N, 表示公园中有初始时有N只野生Cat.

接下来有N行, 每行有3个整数, x, y, z, 表示在(x, y)中有一只野生Cat, 当z0时, 表示是只公♂猫, 否则为母猫.

Output Format

输出公园时刻K时野生Cat的总数.

Sample Input

3 1000007 3
9371 6261 1826 9535 8468 7515
10
0 2 0
2 1 1
2 1 0
1 0 0
1 1 0
1 0 1
2 1 1
2 1 0
1 1 1
1 0 1

Sample Output

694922

Limits

100%的数据 \(A_x, B_x, C_x, A_y, B_y, C_y \leq 10^4\)

10%的数据 \( n \leq 3, K \leq 3,N \leq 10, M \leq 10^7 \)

40%的数据 \( n \leq 5, K \leq 5,N \leq 100, M \leq 10^7 \)

70%的数据 \( n \leq 10, K \leq 100,N \leq 100, M \leq 10^{7} \)

100%的数据 \( n \leq 10, K \leq 100,N \leq 100, M \leq 10^{16} \)

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!