首页 > 其他分享 >Solution Set【2024.1.16】

Solution Set【2024.1.16】

时间：2024-01-16 20:33:27浏览次数：29  
标签：std 2024.1 typedef Set const valueType Solution left mod

A. 硬币

首先根据周长最大的要求不难发现我们实际上要求的是 \(n^2 + 1\) 的最小质因子，记作 \(f_n\)，通过观察可以发现若对于个 \(t\)，满足存在 \(p\) 使得

\[p \mid t^2 + 1 \]

那么对于所有 \(k \ge 0\)，一定有

\[p \mid \left(t + k \cdot p\right)^2 + 1 \]

因此我们可以维护一个序列 \(a\)，初始时满足 \(a_i = i^2 + 1\)。我们从小到大枚举 \(i\)，找到 \(a_i\) 的最小质因子 \(p\)，然后对于所有满足 \(j \ge i\) 且 \(j \equiv i \pmod p\) 的 \(j\)，除去 \(a_j\) 的所有质因子 \(p\)，并更新 \(f_j \leftarrow \min\left\{f_j, p\right\}\)。

下面证明每次遍历到的 \(i\)，一定满足 \(a_i\) 为质数。我们尝试通过归纳证明遍历到的 \(a_i\) 均为 \(1\) 或 \(i^2 + 1\) 的最大质因子。

首先，对于 \(i = 1\)，显然 \(a_i = 2\) 为质数，满足条件。

对于 \(i > 1\)，首先我们可以发现对于任意质数 \(p\)，均有

\[p \nmid p^2 + 1 \]

因此我们只需要考虑 \(< i\) 和 \(> i\) 的质因子即可。我们可以发现，对于任意质数 \(p\)，我们有：

\[p \mid i^2 + 1 \rightarrow p \mid \left(i \bmod p\right)^2 + 1 \]

因此对于所有 \(< i\) 的质因子，其一定在 \(i \bmod p < i\) 的位置出现过，因此当遍历到 \(i\) 时，其一定不在 \(a_i\) 中。

同时不难发现在 \(i^2 + 1\) 中至多存在一个 \(> i\) 的质因子，因此我们可以得到结论。

Code 
#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;

constexpr valueType V = 1000000;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

#ifndef LOCAL_STDIO
    freopen("coins.in", "r", stdin);
    freopen("coins.out", "w", stdout);
#endif

    ValueVector ans(V + 1, std::numeric_limits<valueType>::max() >> 1), F(V + 1, 0);

    for (valueType i = 1; i <= V; ++i)
        F[i] = i * i + 1;

    for (valueType i = 1; i <= V; ++i) {
        if (F[i] == 1)
            continue;
        
        ans[i] = std::min(ans[i], F[i]);

        valueType const x = F[i];

        while (F[i] % x == 0)
            F[i] /= x;

        for (valueType j = i; j <= V; j += x) {
            ans[j] = std::min(ans[j], x);

            while (F[j] % x == 0)
                F[j] /= x;
        }
    }

    valueType T;

    std::cin >> T;

    for (valueType testcase = 0; testcase < T; ++testcase) {
        valueType N;

        std::cin >> N;

        if (ans[N] >= N)
            std::cout << -1 << '\n';
        else
            std::cout << ans[N] << ' ' << (N * N + 1) / ans[N] << '\n';
    }

    std::cout << std::flush;

    return 0;
}

回到问题开始，我们实要求的是 \(n^2 + 1\) 的最小质因子，即满足

\[n^2 \equiv -1 \pmod p \]

的最小质数 \(p\)。首先可以发现，\(n^2 + 1\) 的最小质因子 \(p\) 一定满足 \(p \le n\)，因此我们可以枚举 \(p\)，然后求出其二次剩余根，后更新答案。

Code 
#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<bool> bitset;

namespace MODINT_WITHOUT_MOD {
    template<typename T1, typename T2, typename T3 = valueType>
    void Inc(T1 &a, T2 b, const T3 &mod) {
        a = a + b;

        if (a >= mod)
            a -= mod;
    }

    template<typename T1, typename T2, typename T3 = valueType>
    void Dec(T1 &a, T2 b, const T3 &mod) {
        a = a - b;

        if (a < 0)
            a += mod;
    }

    template<typename T1, typename T2, typename T3 = valueType>
    T1 sum(T1 a, T2 b, const T3 &mod) {
        return a + b >= mod ? a + b - mod : a + b;
    }

    template<typename T1, typename T2, typename T3 = valueType>
    T1 sub(T1 a, T2 b, const T3 &mod) {
        return a - b < 0 ? a - b + mod : a - b;
    }

    template<typename T1, typename T2, typename T3 = valueType>
    T1 mul(T1 a, T2 b, const T3 &mod) {
        return (long long) a * b % mod;
    }

    template<typename T1, typename T2, typename T3 = valueType>
    void Mul(T1 &a, T2 b, const T3 &mod) {
        a = (long long) a * b % mod;
    }

    template<typename T1, typename T2, typename T3 = valueType>
    T1 pow(T1 a, T2 b, const T3 &mod) {
        T1 result = 1;

        while (b > 0) {
            if (b & 1)
                Mul(result, a, mod);

            Mul(a, a, mod);
            b = b >> 1;
        }

        return result;
    }
}// namespace MODINT_WITHOUT_MOD

using namespace MODINT_WITHOUT_MOD;

class Complex {
    valueType _real;
    valueType _imag;

public:
    Complex() = default;

    Complex(valueType real, valueType imag = 0) : _real(real), _imag(imag) {}

    friend Complex Mul(const Complex &a, const Complex &b, valueType omega, valueType mod) {
        return Complex(
                sum(mul(a._real, b._real, mod), mul(omega, mul(a._imag, b._imag, mod), mod), mod),
                sum(mul(a._real, b._imag, mod), mul(a._imag, b._real, mod), mod));
    }

    friend Complex Pow(Complex a, valueType b, valueType omega, valueType mod) {
        Complex result(1, 0);

        while (b > 0) {
            if (b & 1)
                result = Mul(result, a, omega, mod);

            a = Mul(a, a, omega, mod);
            b = b >> 1;
        }

        return result;
    }

    valueType real() const {
        return _real;
    }

    valueType imag() const {
        return _imag;
    }
};

valueType Legendre(valueType n, valueType p) {
    if (n % p == 0)
        return 0;

    if (pow(n, (p - 1) / 2, p) == 1)
        return 1;
    else
        return -1;
}

valueType Cipolla(valueType n, valueType p) {
    static std::mt19937 engine(std::chrono::steady_clock::now().time_since_epoch().count() ^ std::random_device()() ^ (unsigned long long) std::make_unique<char>().get());

    n %= p;

    if (Legendre(n, p) == -1)
        return -1;

    valueType A, omega;

    while (true) {
        A = engine() % p;

        omega = sub(mul(A, A, p), n, p);

        if (Legendre(omega, p) == -1)
            break;
    }

    Complex I(A, 1);

    I = Pow(I, (p + 1) / 2, omega, p);

    return I.real();
}

constexpr valueType V = 1000000;

std::array<valueType, V + 5> ans;

ValueVector GetPrime(valueType n) {
    bitset isPrime(n + 1, true);
    ValueVector prime;

    prime.reserve(n);

    isPrime[0] = isPrime[1] = false;

    for (valueType i = 2; i <= n; ++i) {
        if (isPrime[i])
            prime.push_back(i);

        for (auto const &j : prime) {
            valueType const t = i * j;

            if (t > n)
                break;

            isPrime[t] = false;

            if (i % j == 0)
                break;
        }
    }

    return prime;
}


int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

#ifndef LOCAL_STDIO
    freopen("coins.in", "r", stdin);
    freopen("coins.out", "w", stdout);
#endif

    valueType T;

    std::cin >> T;

    ans.fill(-1);

    ValueVector const Prime = GetPrime(V);

    for (valueType i = 1; i <= V; i += 2)
        ans[i] = 2;

    for (auto const &p : Prime) {
        if (p == 2)
            continue;

        valueType const X = Cipolla(p - 1, p);

        if (X == -1)
            continue;

        valueType const Y = p - X;

        for (valueType i = X; i <= V; i += p)
            if (ans[i] == -1)
                ans[i] = p;

        for (valueType i = Y; i <= V; i += p)
            if (ans[i] == -1)
                ans[i] = p;
    }

    for (valueType testcase = 0; testcase < T; ++testcase) {
        valueType N;

        std::cin >> N;

        valueType const M = N * N + 1;

        if (ans[N] == -1 || ans[N] == M)
            std::cout << -1 << '\n';
        else
            std::cout << ans[N] << ' ' << M / ans[N] << '\n';
    }

    std::cout << std::flush;

    return 0;
}

B. 猜数

首先不难得到一个 \(\mathcal{O}(n^3)\) 的 DP，设 \(f_{l, r}\) 表示在确保需要猜的数在 \([l, r]\) 时，猜出其的最优花费，通过枚举这一次猜的数 \(k\)，我们有转移：

\[f_{l, r} = \min\limits_{l \le k \le r}\left\{k + \max\left\{f_{l, k - 1}, f_{k, k}, f_{k + 1, r}\right\}\right\} \]

不难发现无论如何 \(f_{k ,k}\) 均不会取到最大值，因此转移式可以简化为：

\[f_{l, r} = \min\limits_{l \le k \le r}\left\{k + \max\left\{f_{l, k - 1}, f_{k + 1, r}\right\}\right\} \]

发现在 \(l\) 一定，\(r\) 增加的过程对于某个 \(k\) 有 \(f_{l, k - 1}\) 保持不变，\(f_{k + 1, r}\) 单调递增，因此我们可以设 \(k_0\) 表示满足 \(f_{l, k - 1} \le f_{k + 1, r}\) 的最小 \(k\)，每次转移时只需要考虑 \(k \in \left[l, k_0\right)\) 和 \(k \in \left(k_0, r\right]\) 两部分贡献即可。

  • 对于 \(k \in \left[l, k_0\right)\)，其决策集合只增大不减小，因此使用单变量维护即可。

  • 对于 \(k \in \left(k_0, r\right]\)，随着 \(r\) 的增加，\(k_0\) 一定不会减小，因此我们可以使用单调队列维护。

复杂度为 \(\mathcal{O}(n^2)\)。可以发现对答案序列进行三次差分操作后非零项的数量很少，因此将三次差分后的序列的所有非零项打表即可。

$\mathcal{O}(n^2)$ 
#include <bits/stdc++.h>

typedef int valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
typedef std::pair<valueType, valueType> ValuePair;
typedef std::deque<ValuePair> PairDeque;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType N;

    std::cin >> N;

    ValueMatrix F(N + 1);

    for (valueType i = 1; i <= N; ++i)
        F[i].resize(N - i + 2, 0);

    for (valueType r = 2; r <= N; ++r) {
        valueType k = r - 1;

        PairDeque left;

        for (valueType l = r - 1; l > 0; --l) {
            while (F[l][k - 1 - l + 1] > F[k + 1][r - (k + 1) + 1]) {
                if (!left.empty() && left.front().second == k)
                    left.pop_front();

                --k;
            }

            valueType const next = l + F[l + 1][r - (l + 1) + 1];

            while (!left.empty() && next < left.back().first)
                left.pop_back();

            left.emplace_back(next, l);

            F[l][r - l + 1] = std::min(left.front().first, F[l][k - l + 1] + k + 1);
        }
    }

    for (valueType i = 1; i <= N; ++i) {
        std::cout << F[1][i] << '\n';
    }

    std::cout << std::flush;

    return 0;
}
打表程序 
#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::pair<valueType, valueType> ValuePair;
typedef std::vector<ValuePair> PairVector;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    constexpr valueType N = 50000;

    ValueVector A(N + 1, 0);// 原序列

    for (valueType i = 1; i <= N; ++i)
        std::cin >> A[i];

    ValueVector B(N + 1, 0);// 差分序列

    for (valueType i = 1; i <= N; ++i)
        B[i] = A[i] - A[i - 1];

    ValueVector C(N + 1, 0);// 差分序列的差分序列

    for (valueType i = 1; i <= N; ++i)
        C[i] = B[i] - B[i - 1];

    PairVector D;// 统计 C 中所有非零元素的位置

    for (valueType i = 1; i <= N; ++i)
        if (C[i] != 0)
            D.emplace_back(i, C[i]);

    ValueVector L(D.size()), R(D.size());

    for (auto i = 0; i < D.size(); ++i) {
        L[i] = D[i].first;
        R[i] = D[i].second;
    }

    std::cout << D.size() << std::endl;

    std::cout << '{';

    for (auto i = 0; i < D.size(); ++i)
        std::cout << L[i] << ",}"[i + 1 == D.size()];

    std::cout << std::endl;

    std::cout << '{';

    for (auto i = 0; i < D.size(); ++i)
        std::cout << R[i] << ",}"[i + 1 == D.size()];

    std::cout << std::endl;

    return 0;
}
提交程序 
#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;

constexpr valueType N = 50000;
constexpr valueType D = 593;
constexpr std::array<valueType, D> L = {2, 4, 12, 16, 20, 32, 40, 48, 52, 80, 96, 112, 124, 146, 147, 148, 152, 192, 224, 256, 284, 309, 310, 312, 344, 357, 358, 360, 368, 448, 512, 576, 636, 664, 666, 667, 693, 694, 704, 792, 800, 848, 928, 936, 1040, 1056, 1064, 1168, 1184, 1192, 1296, 1312, 1320, 1404, 1440, 1442, 1443, 1466, 1467, 1477, 1478, 1536, 1562, 1563, 1664, 1680, 1752, 1754, 1755, 1856, 1872, 1904, 2000, 2008, 2085, 2086, 2096, 2112, 2348, 2352, 2368, 2604, 2608, 2624, 2860, 2864, 2880, 3068, 3112, 3116, 3142, 3143, 3148, 3149, 3210, 3211, 3237, 3238, 3301, 3302, 3306, 3307, 3370, 3371, 3388, 3432, 3436, 3462, 3463, 3468, 3469, 3472, 3568, 3572, 3712, 3722, 3723, 3736, 3920, 3952, 3956, 4096, 4106, 4107, 4120, 4208, 4344, 4352, 4432, 4464, 4608, 4656, 4720, 4960, 4992, 5192, 5232, 5472, 5504, 5704, 5744, 5984, 6016, 6216, 6256, 6496, 6528, 6652, 6700, 6704, 6748, 6756, 6816, 6842, 6843, 6912, 6917, 6918, 6986, 6987, 7045, 7046, 7108, 7112, 7178, 7179, 7200, 7395, 7396, 7456, 7482, 7483, 7552, 7557, 7558, 7626, 7627, 7636, 7692, 7696, 7840, 7850, 7851, 7864, 8144, 8160, 8185, 8186, 8364, 8365, 8371, 8372, 8640, 8912, 8928, 8953, 8954, 9132, 9133, 9139, 9140, 9200, 9376, 9392, 9504, 9536, 9728, 9744, 9760, 9769, 9770, 9920, 9936, 10128, 10272, 10288, 10400, 10421, 10422, 10681, 10682, 10688, 10944, 11072, 11440, 11445, 11446, 11705, 11706, 11712, 11968, 12096, 12464, 12469, 12470, 12729, 12730, 12736, 12992, 13120, 13488, 13493, 13494, 13753, 13754, 13760, 14016, 14144, 14332, 14384, 14388, 14440, 14456, 14549, 14550, 14576, 14650, 14651, 14656, 14730, 14731, 14789, 14790, 14860, 14862, 14933, 14934, 14954, 14955, 15104, 15168, 15212, 15272, 15276, 15338, 15339, 15360, 15509, 15510, 15548, 15592, 15856, 15888, 16080, 16140, 16142, 16213, 16214, 16234, 16235, 16384, 16448, 16470, 16471, 16569, 16570, 16572, 16576, 16704, 16768, 16992, 17152, 17480, 17496, 17664, 17792, 17811, 17812, 17909, 17910, 17911, 17936, 18240, 18368, 18976, 19016, 19032, 19200, 19328, 19347, 19348, 19445, 19446, 19447, 19472, 19776, 19904, 19952, 20144, 20160, 20352, 20416, 20672, 20752, 20896, 20904, 21010, 21011, 21012, 21109, 21110, 21111, 21136, 21168, 21376, 21392, 21568, 21610, 21611, 22208, 22464, 22544, 22688, 22696, 22752, 22933, 22935, 22940, 23200, 23232, 23248, 23296, 23936, 24128, 24192, 24528, 24560, 25088, 25248, 25280, 25296, 25344, 25984, 26176, 26240, 26576, 26608, 27136, 27296, 27328, 27344, 27392, 28032, 28224, 28288, 28624, 28656, 29184, 29344, 29376, 29392, 29440, 30080, 30272, 30336, 30672, 30704, 30716, 30772, 30776, 30832, 30848, 30960, 31000, 31112, 31120, 31232, 31296, 31312, 31392, 31397, 31398, 31477, 31478, 31488, 31496, 31616, 31738, 31739, 31818, 31819, 31824, 31904, 31925, 31926, 32085, 32086, 32138, 32139, 32298, 32299, 32309, 32310, 32448, 32576, 32624, 32693, 32694, 32698, 32699, 32778, 32779, 32800, 32960, 33013, 33014, 33216, 33232, 33237, 33238, 33546, 33547, 33552, 33664, 33728, 33736, 34048, 34080, 34208, 34234, 34235, 34256, 34848, 34858, 34859, 34869, 34870, 35008, 35136, 35184, 35253, 35254, 35258, 35259, 35338, 35339, 35360, 35504, 35580, 35584, 35776, 35808, 35824, 36192, 36272, 36448, 36480, 36864, 36896, 36922, 36923, 36944, 37088, 37504, 37536, 37760, 37781, 37782, 37970, 37971, 38000, 38069, 38070, 38074, 38075, 38154, 38155, 38176, 38224, 38528, 38560, 38912, 39040, 39680, 39808, 39840, 39861, 39862, 40480, 40512, 40528, 41064, 41072, 41141, 41142, 41146, 41147, 41226, 41227, 41248, 41296, 41600, 41632, 41984, 42112, 42752, 42880, 42912, 42933, 42934, 43056, 43264, 43280, 43488, 43552, 43904, 44064, 44284, 44292, 44416, 44426, 44427, 44448, 44488, 44704, 44720, 44928, 44992, 45397, 45398, 45440, 45744, 45968, 45984, 46186, 46187, 46229, 46230, 46608, 46720, 46736, 46912, 47552, 47584, 48064, 48072, 48288, 48304, 48512, 48576, 48981, 48982, 49024, 49098, 49099, 49258, 49259, 49269, 49270, 49504, 49616, 49621, 49622};
constexpr std::array<valueType, D> R = {1, 1, 1, 1, -1, 1, 1, 1, -2, 1, 1, 1, -2, 1, 2, -2, -1, 1, 1, 1, -2, 2, 1, -3, 1, 2, 1, -3, -1, 1, 1, 1, -2, 3, -1, -2, 2, 1, -3, 4, -3, -1, 2, -2, 1, 2, -2, 1, 2, -2, 1, 2, -2, -2, 3, -1, -2, 1, 2, -2, -1, 3, -1, -2, 1, -1, 4, -1, -2, 1, -1, -1, 2, -2, 2, 1, -1, -2, 4, -1, -2, 4, -1, -2, 4, -1, -2, -2, 2, -2, 3, 2, -1, -4, 1, 2, -2, -1, 2, 1, -1, -2, 1, 2, -2, 2, -2, 3, 2, -1, -4, -1, 4, -4, 1, 1, 2, -4, 1, 4, -4, 1, 1, 2, -4, -1, 2, -2, 2, -2, 2, -1, -1, 1, -1, 2, -1, 1, -1, 2, -1, 1, -1, 2, -1, 1, -1, -2, 2, -2, 4, -4, 3, -1, -2, 3, -2, -1, 1, 2, -2, -1, 4, -4, 1, 2, -3, 4, -3, 3, -1, -2, 3, -2, -1, 1, 2, -4, 4, -4, 1, 1, 2, -4, 2, 3, -2, -3, 1, 4, -4, -1, 1, 2, 3, -2, -3, 1, 4, -4, -1, -1, 1, -1, 2, -2, 2, 2, 3, -6, -1, 2, -2, 1, 1, -1, 2, -2, -1, 2, 3, -5, 1, -1, 4, -2, -1, 2, 3, -5, 1, -1, 4, -2, -1, 2, 3, -5, 1, -1, 4, -2, -1, 2, 3, -5, 1, -1, -2, 2, -2, 2, -2, 2, 1, -3, 1, 2, -3, 1, 2, -2, -1, 8, -8, 2, 1, -1, -2, 3, 1, -4, 4, -4, 1, 2, -3, 2, 1, -2, -1, 1, -1, 1, 8, -8, 2, 1, -1, -2, 3, 1, -3, -2, 2, 3, -4, -1, 1, -1, 1, -1, 2, -2, 2, 3, -4, -1, 4, -1, -2, -1, 1, -1, 1, 2, -2, 2, 3, -4, -1, 4, -1, -2, -1, 1, -1, -1, 1, -1, 1, -1, 2, -2, 4, -4, 5, -2, -1, 4, -1, -2, -1, -2, 2, -2, 3, -1, -2, 1, 2, -2, 4, -4, -1, 6, -2, -4, 1, 2, -2, -1, 1, 1, -2, 2, -2, 1, 1, 2, -2, -1, 1, 1, -2, 2, -2, 1, 1, 2, -2, -1, 1, 1, -2, 2, -2, 1, 1, 2, -2, -1, 1, 1, -2, 2, -2, -2, 2, -2, 2, -2, 2, -2, 2, -2, 2, 1, -3, 3, -2, -1, 2, 1, 1, -4, 3, -1, -2, 1, 2, -3, 3, -2, -1, 2, 1, -1, -2, 1, 2, -2, -1, 4, 1, -5, 2, 1, -1, -2, 1, 2, -3, 3, -2, -1, 1, 2, -2, -1, 1, 2, -2, 2, 1, -4, 1, -1, 4, -1, -2, -1, 1, 1, 2, -2, -1, 4, 1, -5, 2, 1, -1, -2, 1, 2, -3, -1, 4, -4, 1, 1, -2, 2, -2, 1, -1, 1, 4, -1, -2, -1, -1, 1, -1, 6, -4, -2, 5, 2, -5, 2, 1, -1, -2, 1, 2, -3, -2, 1, -1, 1, -1, 1, 1, 4, -4, -2, 1, 1, -2, 8, -5, 2, 1, -1, -2, 1, 2, -3, -2, 1, -1, 1, -1, 1, 1, 4, -4, -2, -1, 1, -1, 1, -1, 1, -1, 4, -4, 4, 1, 2, -3, -4, 2, -2, 2, -2, 2, 1, -1, -2, 2, -2, 1, 2, -2, -1, 1, 1, -1, -1, 2, -2, 5, -4, 2, -2, 2, -2, 2, 1, -1, -1, -2, 1, 2, -2, -1, 1, 2, -2, -1};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

#ifndef LOCAL_STDIO
    freopen("guess.in", "r", stdin);
    freopen("guess.out", "w", stdout);
#endif

    ValueVector A(N + 1, 0);

    for (valueType i = 0; i < D; ++i)
        A[L[i]] = R[i];

    std::partial_sum(A.begin(), A.end(), A.begin());
    std::partial_sum(A.begin(), A.end(), A.begin());
    std::partial_sum(A.begin(), A.end(), A.begin());

    valueType n;

    std::cin >> n;

    std::cout << A[n] << std::endl;

    return 0;
}

C. 卡片 / ARC112F Die Siedler

首先不考虑操作 \(2\)，那么我们可以发现执行 \(1\) 操作一定不劣，因此我们可以将所有的 \(1\) 操作全部执行完毕。

考虑执行 \(1\) 操作的过程，定义 \(c_i\) 表示第 \(i\) 种牌的数量。

  • 对于 \(1 \le i < N\)，若 \(c_i \ge 2 \cdot i\)，那么有 \(c_i \leftarrow c_i - 2 \cdot i, c_{i + 1} \leftarrow c_{i + 1} + 1\)

  • 若 \(c_N \ge 2 \cdot N\)，那么有 \(c_N \leftarrow c_N - 2 \cdot N, c_{1} \leftarrow c_{1} + 1\)

考虑将 \(c_i\) 视作一个多进制数，那么其答案即为其数位之和，其中第一种情况便是其进位方法，进而我们可以将其转化为一个十进制数，不难发现其值为：

\[\sum\limits_{i}c_i \times 2^{i - 1} \times \left(i - 1\right)! \]

其中 \(2^{i - 1} \times \left(i - 1\right)! = \prod\limits_{j \equiv i \pmod 2} j\)。

考虑到第二种情况的存在，其十进制数实际上值为减去 \(B = 2^N \times N!\) 后的结果。

进而我们可以发现，对于每个十进制数，我们可以求出其代表状态的答案。

因此考虑如何处理 \(2\) 操作，不难发现 \(2\) 操作实际上是直接对十进制数上加上某个值，不妨设为 \(a_i\)。

设 \(S = \sum\limits_{i}c_i \times 2^{i - 1} \times \left(i - 1\right)!\)，即初始状态。那么对于所有可达状态 \(b\)，通过枚举第 \(i\) 种卡包的使用数量 \(x_i\) 和十进制数减去的 \(B\) 的数量 \(y\)，我们有：

\[T = S + \sum\limits_{i}a_i \cdot x_i - y \times B \]

即

\[T - S = \sum\limits_{i}a_i \cdot x_i - y \times B \]

根据裴蜀定理，设 \(d = \gcd\left\{B, \gcd\limits_{i} a_i\right\}\)，我们有

\[d \mid T - S \]

由于十进制数中已经减去了所有的 \(B\)，因此我们有 \(0 \le T < B\)。

考虑按 \(d\) 的大小进行分治。

  • 当 \(d\) 较大时，可能的 \(T\) 值的数量很小，因此我们可以直接枚举 \(T\)，然后计算其答案并取最小值即可。复杂度为 \(\mathcal{O}(\frac{2^n \times n!}{d})\)

  • 当 \(d\) 较小时，我们考虑计算使得状态 \(T \equiv S \pmod B\) 所需要使用的最小牌数，使用同余最短路即可。具体的，对于所有 \(u \in \left[0, d\right)\)，我们建边 \(u \rightarrow \left(u + 2^i \times i!\right)\)。求 \(dist_{S \bmod b}\) 即可，特别的，由于不存在没有卡牌的情况，所以要求最短路中至少存在一条边。复杂度为 \(\mathcal{O}(nd)\)

对所有的 \(2^n \times n!\) 的值进行分解因数可以发现，对于所有 \(n \le 16\)，\({2^n \times n!}\) 的不超过 \({2^n \times n!}\) 的最大因子为 \(1214827\)，因此上述做法可以在本题中通过。

代码 
#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
typedef std::queue<valueType> ValueQueue;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

#ifndef LOCAL_STDIO
    freopen("card.in", "r", stdin);
    freopen("card.out", "w", stdout);
#endif

    valueType N, M;

    std::cin >> N >> M;

    ValueVector Base(N + 1, 1);

    for (valueType i = 1; i <= N; ++i)
        Base[i] = Base[i - 1] * (2 * i);

    auto Calc = [&](ValueVector const &a) -> valueType {
        valueType result = 0;

        for (valueType i = 1; i <= N; ++i)
            result += a[i] * Base[i - 1];

        return result;
    };

    auto F = [&](valueType x) -> valueType {
        valueType result = 0;

        for (valueType i = 1; i <= N; ++i) {
            result += x % (2 * i);
            x /= (2 * i);
        }

        return result;
    };

    ValueMatrix A(M + 1, ValueVector(N + 1, 0));

    for (valueType i = 0; i <= M; ++i) {
        for (valueType j = 1; j <= N; ++j)
            std::cin >> A[i][j];

        A[i][0] = Calc(A[i]);
    }

    if (A[0][0] == 0) {
        std::cout << 0 << std::endl;

        return 0;
    }
 
    valueType gcd = Base[N] - 1;

    for (valueType i = 1; i <= M; ++i)
        gcd = std::__gcd(gcd, A[i][0]);

    if (gcd > std::sqrt(Base[N])) {
        valueType ans = std::numeric_limits<valueType>::max();

        valueType const S = A[0][0];

        for (valueType s = (S % gcd == 0 ? gcd : S % gcd); s < Base[N]; s += gcd)
            ans = std::min(ans, F(s));

        std::cout << ans << std::endl;

        return 0;
    }

    ValueMatrix G(gcd);

    for (valueType i = 0; i < N; ++i) {
        for (valueType j = 0; j < gcd; ++j)
            G[j].push_back((j + Base[i]) % gcd);
    }

    valueType const S = 0, T = A[0][0] % gcd;

    ValueVector dist(gcd, std::numeric_limits<valueType>::max());

    ValueQueue Q;

    for (auto const &to : G[S]) {
        dist[to] = 1;

        Q.push(to);
    }

    while (!Q.empty()) {
        valueType const x = Q.front();

        Q.pop();

        for (auto const &to : G[x]) {
            if (dist[to] > dist[x] + 1) {
                dist[to] = dist[x] + 1;

                Q.push(to);
            }
        }
    }

    std::cout << dist[T] << std::endl;

    return 0;
}

标签：std,2024.1,typedef,Set,const,valueType,Solution,left,mod
From： https://www.cnblogs.com/User-Unauthorized/p/-/2024-1-16

相关文章

  • 2024.1.16-每日进度笔记
    今天，尝试在jsp中上传图片并进行预览，同时将上传的图片等比例缩小到预览区域内。 参考：百度文心一言的回复。 <%@pagelanguage="java"contentType="text/html;charset=UTF-8"pageEncoding="UTF-8"%><!DOCTYPEhtml><html><head><metacharset=&qu......
  • Apple开发_在一个类中同时重写set和get方法发生冲突的解决办法
    平常我们在一个类中只重写属性set或get方法，系统都会自动生成一个带有下划线的属性；但是我们有时候需要同时重写set和get方法，系统就不会自动生成带有下划线的属性了，会报错，如下图：要解决这个问题，只需要用@synthesize来解决这个问题，如：......
  • 【开源项目推荐】——纯中文本地GPT知识库搭建项目.assets
    大家好，我是独孤风。又到了本周的开源项目推荐。近一年多的时间，人工智能迎来了大爆发。GPT相关的大模型的发展让很多领域都发生了巨大的变化。但是虽然GPT的自然语言识别功能异常的强大，但回答给我们的知识内容并不尽如人意。那么，有没有可以在本地部署搭建的AI知识库项目呢？今天为......
  • 2024.1
    1.P3780[SDOI2017]苹果树首先要转化一下\(t-h\lek\)这个限制，考虑它的实际意义，就是我们取出所选的点中最深的一个，记为\(x\)，从根到它每个点都能免费领一个苹果。那我们反过来枚举\(x\)，尝试计算答案。按普通的方式进行树形dp是\(O(nk^2)\)的，瓶颈在于我们合并两个背包......
  • Redis - Sorted Set Use Cases
         ......
  • Redis - Set Use Cases
          ......
  • 南外集训 2024.1.15 T3
    纯粹技术性的题目。给定一个字符串的后缀数组以及对应的height数组的一部分（即一些height数组的位置是未知的，用\(-1\)表示），要求还原出一种可能的字符串。保证存在一种由\(26\)个小写英文字母构成的解。\(1\len\le10^6\)首先考虑没有\(-1\)的情况。注意到此时我们给......
  • 2024.1.15-每日进度笔记
    今天，我尝试在java中对昨天的python脚本进行调用，并尝试对输出结果进行格式化。 参考：百度文心一言的回复。 packagetest0113;importjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;importjava.util.Arrays;publicclasstes......
  • js Set方法
    ECMAScript6新增的Set是一种新集合类型，为这门语言带来集合数据结构。Set在很多方面都像是加强的Map，这是因为它们的大多数API和行为都是共有的。1.基本API：使用new关键字和Set构造函数可以创建一个空集合:constm=newSet();如果想在创建的同时初始化实例，则可以给Set......
  • 南外集训 2024.1.12 T3/AGC022F Checkers 加强版
    第一步转化比较套路，DP设计需要很强的洞察力，最后的优化也很考验基本功。有\(n\)个\(n\)维空间中的点，第\(i\)个点\(x_i\)满足\(x_{i,i}=1,x_{i,j}=0(\foralli\neqj)\)。接下来进行\(n-1\)次操作，每次任选两个点，将第一个点关于第二个点对称，然后删掉第二个点。......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99