自动搬运

查看原文

来自洛谷，原作者为

	Walrus OI（22.7~25.7）||节目有点不伦不类，川剧，古代服饰，沂蒙山歌，和绍兴有啥关系，没得江南水乡的半点意思，不是绍剧，是苕皮。

搬运于2025-08-24 21:47:15，当前版本为作者最后更新于2024-10-02 01:52:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Tips（写在前面）

由于此题为分类讨论题，故此文章与写代码同步进行并同步更新。

为了方便描述，下称：

• $1$ 倍镖为 $1$ 镖（其余同理）。

引入个重要结论（不打红心）：

任意在 $5\sim 5\times k_i$ 之间的数均可被两次数字镖（一次 $2$ 镖一次 $3$ 镖）打出来，特别的，$5\times k_i-1$ 不行，且 $5\times k + 1\sim 6\times k$ 中的 $3$ 的倍数可以被打出来（理论上 $2\sim 4$ 也可以被打出来，但便于表述准确不将二者混为一谈）。

故无解的情况就比较简单了。

简单证明：

• 方法一：豆豆大法，即根据同余拼出需要的余数 $x\equiv p\pmod 5$。其中 $x$ 为需要拼的数。

• 方法二：分类讨论 $5$ 种模数的情况，均可表示为 $2\times x+3\times y$ 的形式，且 $x,y$ 满足 $x,y\leq k$。这里自行证明或参考其他题解。

只提一下为什么 $5\times k-1$ 不行（较为重要）。

同上，$5\times k - 1=2\times(k+1)+3\times(k-1)$，当 $k$ 取最大时，$k+1$ 越界了，取不到，可以证明不能表示为其他方案使得该数可以被表示出来。

All cases

不一定是对的，根据个人理解，或许与其他题解有出入。

但要注意很重要的一点：不一定要用满 $3$ 镖，只要最后一镖是 $2$ 镖即可。所以对于每种情况可能都要多考虑。

由于第三镖较特殊，故将前两镖与第三镖分开讨论。

首先判断情况总数。第三镖显然只有大红心（小红心两倍）或者 $2$ 镖。

而前两镖要讨论红心的个数，位置无所谓。这里假定有红心就先打（即若红心只有一个则打到第一镖）。

故讨论红心个数 $0\sim2$ 个的情况数量。

• $0$ 个，则前两镖都有 $3$ 种倍数可以选择。
• $1$ 个，则第二镖有 $3$ 种倍数可以选择。
• $2$ 个，没得选。

考虑两两组合进行讨论，于是共有 $2\times 3=6$ 种情况。

这里假定前两镖红心个数为 $x$，第三镖是否为红心，用 $x/(0/1)$ 的形式呈现所有情况。

• $0/0$。即全数字，套用上述结论，由于最后一镖必须是 $2$ 镖，所以考虑“融合”两镖配合另一镖打出两镖的效果。所以又有了两种情况。

  • 在 $1\sim 5\times k$ 之间，融合前两镖随便打出 $3$ 镖再配合第三镖当做结论中的 $2$ 镖即可。
  • 反之，要取前两镖中的其中一个 $3$ 镖与第三镖融合，在配合前两镖中的另一镖用结论。

int lt = x - 5 * k;//一次结论后还需要打的，也即 x - 融合镖打的
//case 1
if(2 <= x && lt + 2 <= 2 * k) res = 1;
if(2 <= x && lt + 2 <= 3 * k) res = 1;
//case 2
if(lt % 2 == 0 && (2 <= lt && lt <= 2 * k)) res = 1;
if(lt % 3 == 0 && (0 <= lt && lt <= 3 * k)) res = 1;

• $0/1$。比较简单，直接总数减第三镖打的再用结论。

x -= 2 * m[i];
if(2 <= x && x <= 5 * k && x != 5 * k - 1) res = 1;
if(0 <= x && x <= 6 * k && x % 3 == 0) res = 1;

• $1/0$。因为红心的存在打不到 $6\times k$，只能单独打掉红心，其余同上（Case 2）套结论（这里请注意结论的描述，Case 2 与 Case 3 不能混为一谈）。

x -= 2 * m[i];
if(2 <= x && x <= 5 * k && x != 5 * k - 1) res = 1;

• $1/1$。这种情况也比较简单，直接拼两次红心的倍数，然后判断剩下的数是否可以一镖解决。注意上文提示，此种情况较特殊。

int f0 = x - 2 * m[i],
	f1 = x - 3 * m[i],
	f2 = x - 4 * m[i];//f0 即为特殊处理（只打两镖）
if(f0 >= 0 && ((f0 % 1 == 0 && f0 <= k * 1) || (f0 % 2 == 0 && f0 <= k * 2) || (f0 % 3 == 0 && f0 <= k * 3))) res = 1;
if(f1 >= 0 && ((f1 % 1 == 0 && f1 <= k * 1) || (f1 % 2 == 0 && f1 <= k * 2) || (f1 % 3 == 0 && f1 <= k * 3))) res = 1;
if(f2 >= 0 && ((f2 % 1 == 0 && f2 <= k * 1) || (f2 % 2 == 0 && f2 <= k * 2) || (f2 % 3 == 0 && f2 <= k * 3))) res = 1;

• $2/0$。这种情况同样简单，也是拼两次红心的倍数，判断剩下的数是否可以被最后一镖 $2$ 镖解决。注意上文提示，此种情况较特殊。

int f[5];
rep(j, 0, 4) f[j] = x - j * m[i];
rep(j, 0, 4) {
	if(f[j] % 2 == 0 && (1 <= f[j] / 2 && f[j] / 2 <= k)) {
		res = 1;
		break;
	}
}

• $2/1$。最简单的一集。直接拼三次红心。注意上文提示，此种情况较特殊。

int F[7];
rep(j, 2, 6) F[j] = x - j * m[i];
rep(j, 2, 6) {
	if(F[j] == 0) {
		res = 1;
		break;
	}
}

Code

#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define pre(i, j, k) for(int i = j; i >= k; --i)
#define int long long
#define pb push_back
using namespace std;

const int N = 1e6 + 5;

int n, k[N], m[N], x[N];
int a, b, c, d, ans;

void init() {
	cin >> a >> b >> c >> d >> k[1];
	rep(i, 2, n) k[i] = (a * k[i - 1] % d * k[i - 1] % d + b * k[i - 1] % d + c) % d + 20;
	cin >> a >> b >> c >> d >> m[1];
	rep(i, 2, n) m[i] = (a * m[i - 1] % d * m[i - 1] % d + b * m[i - 1] % d + c) % d + 20;
	cin >> a >> b >> c >> d >> x[1];
	rep(i, 2, n) x[i] = (a * x[i - 1] % d * x[i - 1] % d + b * x[i - 1] % d + c) % d + 20;
}

bool check(int i, int x, string id) {
	int res = 0;
	if(id == "00") {
		int lt = x - 5 * k[i];//一次结论后还需要打的，也即 x - 融合镖打的
		//case 1
		if(2 <= x && lt + 2 <= 2 * k[i]) res = 1;
		if(2 <= x && lt + 2 <= 3 * k[i]) res = 1;
		//case 2
		if(lt % 2 == 0 && (2 <= lt && lt <= 2 * k[i])) res = 1;
		if(lt % 3 == 0 && (0 <= lt && lt <= 3 * k[i])) res = 1;
	}
	if(id == "01") {
		x -= 2 * m[i];
		if(0 <= x && x <= 5 * k[i] && x != 5 * k[i] - 1) res = 1;
		if(0 <= x && x <= 6 * k[i] && x % 3 == 0) res = 1;
	}
	if(id == "10") {
		int f1 = x - 0 * m[i],
		    f2 = x - 1 * m[i],
		    f3 = x - 2 * m[i];
		if(2 <= f1 && f1 <= 5 * k[i] && f1 != 5 * k[i] - 1) res = 1;
		if(2 <= f2 && f2 <= 5 * k[i] && f2 != 5 * k[i] - 1) res = 1;
		if(2 <= f3 && f3 <= 5 * k[i] && f3 != 5 * k[i] - 1) res = 1;
	}
	if(id == "11") {
		int f0 = x - 2 * m[i],
		    f1 = x - 3 * m[i],
		    f2 = x - 4 * m[i];//f0 即为特殊处理（只打两镖）
		if(f0 >= 0 && ((f0 % 1 == 0 && f0 <= k[i] * 1) || (f0 % 2 == 0 && f0 <= k[i] * 2) || (f0 % 3 == 0 && f0 <= k[i] * 3))) res = 1;
		if(f1 >= 0 && ((f1 % 1 == 0 && f1 <= k[i] * 1) || (f1 % 2 == 0 && f1 <= k[i] * 2) || (f1 % 3 == 0 && f1 <= k[i] * 3))) res = 1;
		if(f2 >= 0 && ((f2 % 1 == 0 && f2 <= k[i] * 1) || (f2 % 2 == 0 && f2 <= k[i] * 2) || (f2 % 3 == 0 && f2 <= k[i] * 3))) res = 1;
	}
	if(id == "20") {
		int f[5];
		rep(j, 0, 4) f[j] = x - j * m[i];
		rep(j, 0, 4) {
			if(f[j] % 2 == 0 && (1 <= f[j] / 2 && f[j] / 2 <= k[i])) {
				res = 1;
				break;
			}
		}
	}
	if(id == "21") {
		int F[7];
		rep(j, 2, 6) F[j] = x - j * m[i];
		rep(j, 2, 6) {
			if(F[j] == 0) {
				res = 1;
				break;
			}
		}
	}
	return res;
}

signed main () {
	ios::sync_with_stdio(0);
	cin.tie(nullptr), cout.tie(nullptr);


	cin >> n;
	init();
	rep(i, 1, n) {
		bool f = 0;
		if(check(i, x[i], "00")) f = 1;
		if(check(i, x[i], "01")) f = 1;
		if(check(i, x[i], "10")) f = 1;
		if(check(i, x[i], "11")) f = 1;
		if(check(i, x[i], "20")) f = 1;
		if(check(i, x[i], "21")) f = 1;
		ans += f;
	}

	cout << ans;
	return 0;
}