[??记录]ARC112F Die Siedler

**题意** ： Snuke 使用 $n$ 种卡玩游戏，卡的编号为 $1\sim n$ 。初始时，Snuke 有 $c_i$ 张 $i$ 号卡。 游戏里有 $m$ 种卡组，第 $i$ 种卡组含 $j$ 号卡的数目为 $s_{i,j}$。 可以进行下列操作任意次： - 获取一整套卡组。 - 将 $2j$ 张 $j$ 号牌换成一张 $(j\bmod n)+1$ 号牌。 求 Snuke 手上牌数的最小值。 $n\leq 16,m\leq 50$ ，时限$\texttt{6s}$。 ------------ 神必题。 特判初始没有牌的情况 由于换卡总是有收益，不难证明能换就换是最优的。先用这个规则化简 $c$ 使得 $c_j<2j$ 。 我们把所有卡都倒着换成 $1$ 号卡，个数为 $C=\sum\limits_{i=1}^n2^{i-1}(i-1)!c_i$ 。根据能换就换的原则，这和原问题等价。 然后我们只需考虑仅有 $c_1$ 非零的情况，局面的变换转化为了数的变换。 ------------ 记 $f(X)$ 表示有 $X$ 个 $1$ 号牌，通过适当的交换可以得到的最小牌数，容易贪心 $O(n)$ 求出。 把卡包 $i$ 也转成一个数 $S_i$，使用一次相当于让 $C$ 加上 $S_i$。 注意到我们将 $1$ 换到 $2,3,...,n$ 再换回 $1$ ，可以减少 $2^nn!-1$ 张牌。 操作后 $C$ 的可能取值有 ： $$C'=C+x_1S_1+x_2S_2+...+x_mS_m-y(2^nn!-1)$$ $C'$ 能取到当且仅当 $x_{1\sim m},y$ 有解。根据斐蜀定理，充要条件是 $\gcd(S_1,S_2,...S_m,2^nn!-1)|\big(C'-C\big)$ 记 $d=\gcd(S_1,S_2,...S_m,2^nn!-1)$ ，解集为 $C'=kd+(C\bmod d)$ ，$C'\leq 2^nn!-1$ 。 - 当 $d$ 较大时 直接暴力枚举 $C'$ 并计算 $f(C')$ ，复杂度为 $O(n\times 2^nn!/d)$ - 当 $d$ 较小时 考虑同余最短路。需要求的是满足 $C'=C\pmod d$ 的 $f(C')$ 的最小值。 记 $dis_u$ 为满足 $u=C\pmod d$ 的 $f(u)$ 的最小值。 对于所有 $i\in [0,d),j\in[1,n]$ 从 $i$ 向 $i+2^{j-1}(j-1)!$ 连边，边权为 $1$ ，表示增加一张 $j$ 号牌。 起点是所有 $2^{j-1}(j-1)!$ ，$dis$ 为 $1$ 。（注意不能将起点设为 $0$ 否则 $C=0\pmod d$ 时会出错） 用 BFS ，复杂度为 $O(nd)$ 。 ------------ 哪个算法快用那个，复杂度和 $2^nn!-1$ 的 $\leq\sqrt{2^nn!-1}$ 的最大因子有关。 接下来就是魔法了！[打个表](https://www.wolframalpha.com/input/?i=Table%5B+Factor%5B+n%212%5En-1+%5D%2C+%7Bn%2C2%2C16%7D+%5D)可以发现 $2^nn!-1$ 的 $\leq\sqrt{2^nn!-1}$ 的因数最大值仅有 $1214827$ ，于是本题就做完了。 ```cpp #include<algorithm> #include<cstdio> #include<queue> #include<assert.h> #define ll long long using namespace std; ll gcd(ll a,ll b) {return !b ? a :gcd(b,a%b);} ll w[20];int n; ll calcC(int *c){ ll ret=0; for (int i=1;i<=n;i++)ret+=c[i]*w[i-1]; return ret; } int c[20]; int calcF(ll S) { int ans=0; for (int i=1;i<=n;i++){ans+=S%(2*i);S/=2*i;} return ans; } ll C,d;int m,dis[1220000]; queue<int> q; int main() { scanf("%d%d",&n,&m); w[0]=1;for (int i=1;i<=n;i++)w[i]=w[i-1]*i*2; for (int i=1;i<=n;i++)scanf("%d",&c[i]);C=calcC(c); d=w[n]-1; for (int j=1;j<=m;j++){ for (int i=1;i<=n;i++)scanf("%d",&c[i]); d=gcd(d,calcC(c)); } int ans=1000000000; if (w[n]/d<d){ ll a=C%d;if (!a)a=d; for (ll X=a;X<w[n];X+=d) ans=min(ans,calcF(X)); }else { for (int i=0;i<n;i++){ int u=w[i]%d; if (!dis[u]){dis[u]=1;q.push(u);} } while(!q.empty()){ int u=q.front();q.pop(); for (int i=0,v;i<n;i++){ v=(u+w[i])%d; if (!dis[v]){dis[v]=dis[u]+1;q.push(v);} } }ans=dis[C%d]; } printf("%d",ans); return 0; } ```