题解 P6634【[ZJOI2020] 密码】
whiteqwq
·
·
题解
P6634 [ZJOI2020] 密码 解题报告：
更好的阅读体验
题意
有 m 个方程：
a_ix+b_i\equiv c_i\pmod{mod}
其中 b_i 是 [-\lceil \frac{err}{2}\rceil,\lceil \frac{err}{2}\rceil] 内的随机扰动。
给定 a_i,c_i,mod,err 求 x。
## 分析
若 $err\leqslant 10^6$，可以把方程求和，枚举其扰动，计算出 $x$，check 一下就好了。（没写过，不知道对不对）
不太清楚正解，这里写一下 [skip2004](https://www.cnblogs.com/skip1978/p/13180687.html) 的一种做法。
我们维护当前 $x$ 的范围，不断使用方程缩小其范围，当范围很小时就可以暴力枚举 $x$ 进行 check 了。
我们考虑通过原来的方程加减构造若干个近似程度比较高的方程，然后解出 $x$ 的一个更小范围：
$$ax\pm b\times err\equiv c\pmod{mod}$$
我们不断重复以下流程：
- 随机选择若干个方程（奇数个），并给每个方程随机一个权值 $1/-1$ 然后相加；（期望下 $a,b$ 很小）
- 解出 $x$ 的范围；（需要处理的细节比较多，具体见代码）
- 将新生成的方程按照 $a$ 排序，将相邻的方程相减，生成新的方程。
大概随机几轮就行了。
至于正确性，hzr 说随机加加减减生成的答案可以看做随机，然后可以用 $n$ 个 $[0,V]$ 内随机实数第 $k$ 大期望为 $\frac{Vk}{n+1}$ 的结论缩小范围。
具体还是看 $ 鸽鸽的博客吧，感觉以我的能力讲不清楚。
## 代码
有几个坑点。
rand 要用 mt19937，用自带和手写（这个不确定）的好像都会挂。
每次要给方程扰动一下，否则好像会被卡。
还有一些见代码。
```
struct node{
long long a,c,cnt;
inline bool operator ==(node &p)const{
return a==p.a;
}
inline bool operator <(node &p)const{
return a<p.a;
}
};
int check(long long X){
X=(X%mod+mod)%mod;
int flg=1;
for(int i=1;i<=n;i++){
long long val=dec(mul(a[i],X)-c[i]);
flg&=(val<=err||val>=mod-err);
}
return flg;
}
void addnode(long long a,long long c,long long cnt){
V.push_back(node{a,c,cnt});
if(err>mod/cnt/2||(nowR-nowL+1)>mod/a)
return ;
long long L=mul(nowL,a),R=mul(nowR,a),tmpL=c-cnt*err,tmpR=c+cnt*err;
while(L>R)
R+=mod;
while(tmpL>R)
tmpL-=mod,tmpR-=mod;
while(tmpR<L)
tmpL+=mod,tmpR+=mod;
if(tmpL+mod>R&&tmpR-mod<L)
nowL+=max(tmpL-L,0ll)/a,nowR-=max(R-tmpR,0ll)/a;
}
int main(){
srand(time(0));
scanf("%d",&T);
while(T--){
scanf("%d%lld%lld",&n,&mod,&err),err=(err+1)/2,nowL=0,nowR=mod-1;
for(int i=1;i<=n;i++)
scanf("%lld%lld",&a[i],&c[i]);
while(nowR-nowL+1>S1){
V.clear();
long long delta=rnd()%mod;
nowL+=delta,nowR+=delta;
if(nowR-nowL+1>mod/4)
nowL=0,nowR=mod-1;
for(int i=1;i<=S2;i++){
long long nowA=0,nowC=0;
for(int j=1;j<=S3;j++){
int x=rnd()%n+1;
while(1){
int flg=0;
for(int k=1;k<j;k++)
if(p[k]==x)
flg=1;
if(flg==0)
break;
x=rnd()%n+1;
}
p[j]=x;
long long aa=a[x],cc=inc(c[x]+mul(a[x],delta));
if(rnd()&1)
nowA=inc(nowA+aa),nowC=inc(nowC+cc);
else nowA=dec(nowA-aa),nowC=dec(nowC-cc);
}
addnode(nowA,nowC,(long long)S3);
}
for(int i=1;i<=S4;i++){
if(V.size()>S5)
nth_element(V.begin(),V.begin()+S5,V.end()),V.resize(S5);
sort(V.begin(),V.end()),V.erase(unique(V.begin(),V.end()),V.end());
int rec=V.size();
for(int j=0;j<rec;j++)
for(int k=j+1;k<=j+S6&&k<rec;k++)
addnode(V[k].a-V[j].a,dec(V[k].c-V[j].c),V[j].cnt+V[k].cnt);
}
nowL-=delta,nowR-=delta;
}
ans=0;
for(long long i=nowL;i<=nowR;i++)
if(check(i)){
ans=i;
break;
}
printf("%lld\n",(ans%mod+mod)%mod);
}
return 0;
}
```