P6634 [ZJOI2020] 密码 解题报告
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\)。
\(10^{15}\leqslant p\leqslant 10^{18},1\leqslant err\leqslant\frac{p}{100},50\leqslant m\leqslant 2000\)。
分析
若 \(err\leqslant 10^6\)，可以把方程求和，枚举其扰动，计算出 \(x\)，check 一下就好了。（没写过，不知道对不对）
不太清楚正解，这里写一下 的一种做法。
我们维护当前 \(x\) 的范围，不断使用方程缩小其范围，当范围很小时就可以暴力枚举 \(x\) 进行 check 了。
缩小范围可以随机几个方程加加减减，然后再把结果排个序，相邻的继续相减得到新的方程，再用这些方程去约束一下范围即可。
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=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(tmpRR&&tmpR-modS1){
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;kS5)
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