[ARC112F] Die Siedler - Solution

· · 题解

将整个卡牌序列看作一个「2i」位数，从低到高依次换牌就是进位。

首先注意到换牌操作是严格不劣的，理解大概就是，因为我们是进位，加牌包就是加法，而最后是最小化位数和，贪心的进位最后一定是不劣的。

我们考虑设 c_1 为某一个数 k，然后进位到题目所给的局面，我们发现给定了当前局面那么 k 一定是 \sum\limits_{i=1}^n c_i2^{i-1}(i-1)!。而又根据进位不劣，\{k,\,0,\,0,\,\dots\} 这个局面一定是和题目给定的 c 局面等价的，它们经过最优操作得到的答案一定相等。

因此对于正整数 x，定义 f(x) 为第一种牌有 x 张，进行进位操作后的位数和，也就是答案。

那么就考虑只有第一种牌有 k 张的局面 \text{S}，我们发现其它卡包也可以转化为只有第一张牌的状态，设每个卡包 i 转化后有且只有 d_i 张第一种牌。

这样我们就把初始局面和卡包都转化为了一个数。

还有一点，如果只有 c_1 的状态满足 c_1 \ge 2^nn!，则我们可以依次对 1 \dots n 进行换牌（进位）操作，即我们可以进行任意多次 c_1 \leftarrow c_1 - 2^nn! + 1 的操作。

设每个卡包使用了 x_i 个，同时进行了 y 次减去 2^nn! - 1 的操作，最终局面（答案）为 \text{T}（这里 \text{S} 和 \text{T} 都只是一个数），有：

\text{T} = \text{S} + \left(\sum_{i=1}^{n}d_ix_i\right) - (2^nn! - 1)y

如果设 x_{n + 1} = y，我们发现这就是一个 n + 1 元的不定方程。

\text{T} - \text{S} = \left(\sum_{i=1}^{n}d_ix_i\right) - (2^nn! - 1)y

系数为 \{d_1,\,d_2,\,d_3,\,\dots,\,d_n,\,1-2^nn!\}。

我们并不关心方程的具体解，只关心是否有解。直接使用裴蜀定理，令 G \leftarrow \gcd(d_1,\,d_2,\,d_3,\,\dots,\,d_n,\,2^nn! - 1)，G \mid \text{T} - \text{S} 则方程有解。

设 \text{T} = G \cdot k + \text{S} \bmod G，

直接根号分治看起来复杂度是 \Theta(n\sqrt{2^nn!}) 的，但是经过打表我们得到 2^nn! 不大于 \sqrt{2^nn!} 的最大因数只有 10^6 级别，可以通过。

#include <bits/stdc++.h>
#define X first
#define Y second
#define mp make_pair
#define gc getchar
#define pc putchar
using namespace std;
using ld = double;
typedef long long int ll;
typedef long long int i128;
using pli = pair<ll, int>;
using ppi = pair<pli, int>;
using vec = vector<int>;
constexpr int maxn = 4e6 + 10, S = 4e6, mod = 998244353;
ll gcd(ll n, ll m) { return !m ? n : gcd(m, n % m); }
int q[maxn], d[maxn], hd = 1, tl = 0, n, m; ll a[maxn], p[maxn], G; 
inline ll solve(ll x) {
    ll sum = 0;
    for (int i = 1; i <= n; i++) sum += x % (2 * i), x /= 2 * i;
    return sum;
}
int main() {
    scanf("%d%d", &n, &m); p[0] = 1;
    for (int i = 1; i <= n; i++) p[i] = p[i - 1] * 2 * i; G = p[n] - 1;
    for (int i = 0; i <= m; i++) {
        for (int j = 1, x; j <= n; j++) {
            scanf("%d", &x);
            a[i] = a[i] + p[j - 1] * x;
        }
    }
    for (int i = 1; i <= m; i++) G = gcd(G, a[i]);
    if (G <= S) {
        memset(d, 0x3f, sizeof(d));
        for (int i = 1; i <= n; i++) d[q[++tl] = p[i] % G] = 1;
        while (hd <= tl) {
            int u = q[hd++];
            for (int i = 1; i <= n; i++) {
                int v = (u + p[i]) % G;
                if (d[v] > d[u] + 1) d[q[++tl] = v] = d[u] + 1;
            }
        }
        printf("%d\n", d[a[0] % G]);
    }
    else {
        ll ans = 2e18; ll x = a[0] % G ? a[0] % G : G;
        while (x < p[n]) ans = min(ans, solve(x)), x += G;
        printf("%lld\n", ans);
    }
    return 0;
}