感觉太人类智慧了。
设 \(A = (c_1,c_2,...,c_n)\) 表示当前每种牌的数量,\(f(A)\) 为状态 \(A\) 只进行换牌操作最终最少剩下几张牌。
\(f(A)\) 是可以贪心求出的,因为策略必然是能换则换。
并且我们发现依次换 \(2,3,...,n,1\),最后 \(c_2 \sim c_n\) 都不会变,而 \(c_1 \gets c_1 - (2^n n! - 1)\)。
因为能换则换,所以不妨把 \(i \ge 2\) 的牌全部倒换成 \(1\) 号牌,这样我们得到了现在的 \(c_1 = X = \sum\limits_{i=1}^n c_i 2^{i-1}(i-1)!\)。
显然有 \(f((X,0,0,...,0)) = f(A)\),说明这样做不会影响最终答案。那我们就可以把一个状态映射到一个数 \(X\),对 \(X\) 去考虑就比对 \(A\) 去考虑容易多了。
设 \(P\) 为初始状态全部倒换成 \(1\) 号牌后得到的数,\(a_i\) 为第 \(i\) 套卡包倒换成 \(1\) 号牌后得到的数。设最终答案为 \(Q\),使用了 \(x_i\) 次第 \(i\) 套卡包,进行了 \(y\) 次依次换 \(2,3,...,n,1\) 的操作,那么有如下等式:
发现是一个不定方程的形式。
裴蜀定理:设 \(a,b\) 为不都为 \(0\) 的整数,则 \(ax + by = d\) 有解的充要条件是 \(d \mid \gcd(a,b)\)。
因为裴蜀定理可以推广到多个数,所以 \(Q\) 需要满足:
记 \(d = \gcd(x_1 a_1, x_2 a_2, ..., x_n a_n, 2^n n! - 1)\),令 \(Q = kd + (P \bmod d), k \in \mathbb N\),那么问题就变成了求出 \(\min(f(kd + (P \bmod d)))\)。
我们有两个暴力做法。
- 暴力枚举 \(k\) 并计算,时间复杂度 \(O(n \frac{2^n n! - 1}{d})\)。
- 跑同余最短路,初始是 \(dis_u = 1, u = 2^{i-1} (i-1)!\),每次枚举要拿哪张牌,答案为 \(dis_{P \bmod d}\),时间复杂度 \(O(nd)\)。
考虑根号分治,发现复杂度其实和 \(2^n n! - 1\) 的最大的 \(\le \sqrt{2^n n! - 1}\) 的因数有关。打表可以发现,\(2^n n! - 1\) 的最大的 \(\le \sqrt{2^n n! - 1}\) 的因数为 \(1214827\),可过。
code
// Problem: F - Die Siedler
// Contest: AtCoder - AtCoder Regular Contest 112
// URL: https://atcoder.jp/contests/arc112/tasks/arc112_f
// Memory Limit: 1024 MB
// Time Limit: 6000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 20;
const int maxm = 1220000;
ll n, m, a[maxn], f[maxn], g[maxm];
inline ll calc() {
ll ans = 0;
for (int i = 1; i <= n; ++i) {
ans += a[i] * f[i - 1];
}
return ans;
}
inline ll calc(ll x) {
ll ans = 0;
for (int i = 1; i <= n; ++i) {
ans += (x % (2 * i));
x /= (2 * i);
}
return ans;
}
void solve() {
scanf("%lld%lld", &n, &m);
f[0] = 1;
for (int i = 1; i <= n; ++i) {
f[i] = f[i - 1] * i * 2;
}
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
}
ll P = calc(), d = f[n] - 1;
while (m--) {
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
}
d = __gcd(d, calc());
}
if (d <= 1214827) {
queue<int> q;
mems(g, -1);
for (int i = 0; i < n; ++i) {
g[f[i] % d] = 1;
q.push(f[i] % d);
}
while (q.size()) {
int u = q.front();
q.pop();
for (int i = 0; i < n; ++i) {
int v = (u + f[i]) % d;
if (g[v] == -1) {
g[v] = g[u] + 1;
q.push(v);
}
}
}
printf("%lld\n", g[P % d]);
} else {
ll ans = 9e18;
for (ll x = (P % d ? P % d : d); x < f[n]; x += d) {
ans = min(ans, calc(x));
}
printf("%lld\n", ans);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
到底怎么想到的啊
- AtCoder Regular Contest Siedler 112atcoder regular contest siedler atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest degree atcoder regular contest sliding atcoder regular contest 167 atcoder regular contest 164 atcoder regular contest builder subsegments atcoder regular contest