杂题选做1
[ARC112F] Die Siedler
注意到如果存在某一个 \(j\) 满足这种牌的数量大于等于 \(2j\) ，那么一定会兑换为 \(j \bmod n +1\) 的牌。所以我们考虑这个过程的逆过程，就是将一张牌 \(j\) 换成 \((j-1)!2^{j-1}\) 张 \(1\) 号牌，最终全部的牌都被转化为了 \(1\) 号牌，但是结果并不会改变。记录 \(P=\sum_{i=1}^n c_i 2^{i-1} (i-1)!\) ，表示初始局面 \(1\) 号牌的数量。同理记录 \(b_k=\sum_{i=1}^n a_{k,i}2^{i-1}(i-1)!\) 表示牌堆 \(k\) 经过转化后的 \(1\) 号牌数量。
考虑一组选取牌堆的方案 \(x_1,x_2,\dots,x_n (x_i \geq 0)\) ,最终的 \(1\) 号牌数量为 \(Q=P+\sum_{i=1}^n x_ib_i\) 。这个值可能很大，但是考虑我们将 \(1\) 号牌换成 \(2\) 号牌 ，一直换直到又合成了一张 \(1\) 号牌，中间减少了 \(2^nn!\) 张牌，但是又获得了一张牌。所以 \(Q\) 和 \(Q \bmod (2^nn!-1)\) 是等价的。定义 \(f(Q)\) 表示初始拥有 \(Q(Q <2^nn!)\) 张 \(1\) 号牌，最终会剩下多少牌，具体计算只需要 \(O(n)\) 模拟一下即可。
考虑什么样的 \(Q\) 是可以被表示出来的？那么根据
\[Q \equiv P+\sum_{i=1}^nx_ib_i (\bmod 2^nn!-1) \]得到
\[Q-P \bmod (2^nn!-1)=\sum_{i=1}^n x_ib_i - y\times (2^nn!-1) \]记录 \(d=\gcd(b_1,b_2,\dots,b_n,2^nn!-1)\) ，最终一定需要满足 \(Q-P\bmod (2^nn!-1) =kd\) ，因为 \(d\) 是 \(2^nn!-1\) 的因数，所以这又是 \(Q=kd+P\bmod d\) 。
考虑一个比较有意思的事情，因为有效的 \(Q<2^nn!-1\) 的缘故，\(kd<2^nn!-1\) ，那么 \(k \leq \frac{2^nn!-1}{d}\) ，当 \(d\) 比较大的时候有比较快的速度。\(O(n\frac{2^nn-1}{d})\) 。
那么 \(d\) 比较小的时候怎么办？我们考虑随意填写卡牌，只需要最终全部的卡牌转化为 \(1\) 号牌后，模 \(d\) 的余数为 \(P \bmod d\) 即可，这个过程可以使用同余最短路处理。\(O(nd)\) 。
这个容易想到根号分治。
事实上，在 \(\sqrt{2^nn!-1}\) 以内的 \(d\) 最大为 \(1615037\) 。显而易见的第二种做法符合了时间复杂度。考虑第一种做法的时间最大消耗是啥？\(O(n\frac{2^nn!-1}{1615037})\) 吗？并不是的。第一个大于 \(\sqrt{2^nn!-1}\) 的因数就是 \(e=\frac{\sqrt{2^nn!-1}}{1615037}\) ，带入第一种做法得到时间最劣为 \(O(1615037n)\) ，可以通过。
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int buf[30];
inline void print(int x,char ch=' '){
if(x<0) putchar('-'),x=-x;
int tot=0;
do{
buf[++tot]=x%10;
x/=10;
}while(x);
for(int i=tot;i;i--) putchar(buf[i]+'0');
putchar(ch);
}
const int N=20,inf=1e18;
int n,m,f[N];
int P;
int func(int x){
int ans=0;
for(int i=1;i<=n;i++){
ans+=x%(2*i);
x/=(2*i);
}
return ans;
}
int solve1(int d){
int ans=inf;
for(int i=P%d;i<f[n];i+=d)
if(i) ans=min(ans,func(i));
return ans;
}
int dis[1615037];
int solve2(int d){
memset(dis,-1,sizeof(dis));
queue<int> q;
for(int i=0;i<n;i++)
dis[f[i]%d]=1,q.push(f[i]%d);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0;i<n;i++){
int nxt=(u+f[i])%d;
if(dis[nxt]==-1)
dis[nxt]=dis[u]+1,q.push(nxt);
}
}
return dis[P%d];
}
signed main(){
n=read(),m=read();
f[0]=1;
for(int i=1;i<=n;i++)
f[i]=f[i-1]*2*i;
for(int i=1;i<=n;i++){
int x=read();
P+=x*f[i-1];
}
int d=f[n]-1;
for(int i=1;i<=m;i++){
int sum=0;
for(int j=1;j<=n;j++){
int x=read();
sum+=x*f[j-1];
}
d=__gcd(d,sum);
}
if(d<=1615037) cout<<solve2(d);
else cout<<solve1(d);
return 0;
}
asd