写了一晚上的题

· · 题解

Tips（写在前面）

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

为了方便描述，下称：

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

任意在 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 也可以被打出来，但便于表述准确不将二者混为一谈）。

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

简单证明：

只提一下为什么 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 个的情况数量。

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

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

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;

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;
}