ZR 集训 Day13 – 同余、线代入门

ooliver 发布于 9 小时前 60 次阅读 OI

AI 摘要

一天之内，从NOI屠龙到WC最大XOR路径，从同余最短路到线性基排名，ZR集训带你拆解数论与线代的核心模型！

ZR 集训 Day13 - 同余、线代入门

P4774 [NOI2018] 屠龙勇士

将题目转化为解方程组：

{atack1x≡a1modp1atack2x≡a2modp2…atacknx≡anmodpn\begin{cases} atack_1x\equiv a_1 \mod p_1 \\ atack_2x\equiv a_2 \mod p_2 \\ \dots \\ atack_nx\equiv a_n \mod p_n \end{cases}

显然这是扩展中国剩余定理问题，先用 set 把 $atack$ 数组算出来，在算它的逆元，之后就是 EXCRT 的模板了。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
typedef __int128 i128;
const int N=1e5+5;
int T,n,m,a[N],p[N],atk[N],awd[N];
multiset<int> s;

int exgcd(int a,int b,int &x,int &y){
    if(!b){x=1,y=0;return a;}
    int g=exgcd(b,a%b,x,y);
    int t=x;x=y;y=t-(a/b)*y;
    return g;
}

void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>p[i];
    for(int i=1;i<=n;i++) cin>>awd[i];
    s.clear();
    for(int i=1;i<=m;i++){
        int x;cin>>x;
        s.insert(x);
    }
    for(int i=1;i<=n;i++){
        auto it=s.upper_bound(a[i]);
        if(it!=s.begin()) it--;
        atk[i]=*it;
        s.erase(it);
        s.insert(awd[i]);
    }
    int mx=0;
    for(int i=1;i<=n;i++) mx=max(mx,(a[i]+atk[i]-1)/atk[i]);
    int b1=0,m1=1;
    for(int i=1;i<=n;i++){
        int A=atk[i],B=a[i],P=p[i],x,y;
        int g=exgcd(A,P,x,y);
        if(B%g){cout<<"-1\n";return;}
        A/=g,B/=g,P/=g;
        exgcd(A,P,x,y);
        x=(x%P+P)%P;
        int bi=(i128)B*x%P,mi=P;
        int res=bi-b1;
        int k1,k2;
        g=exgcd(m1,mi,k1,k2);
        if(res%g){cout<<"-1\n";return;}
        int step=mi/g;
        k1=(i128)(res/g)%step*(k1%step)%step;
        if(k1<0) k1+=step;
        b1=b1+(i128)k1*m1;
        m1=m1/g*mi;
        b1=(b1%m1+m1)%m1;
    }
    int ans=b1;
    if(ans<mx) ans+=(mx-ans+m1-1)/m1*m1;
    cout<<ans<<"\n";
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--) solve();
    return 0;
}

P3846 【模板】BSGS / [TJOI2007] 可爱的质数

BSGS（baby-step giant-step）算法模板题。

对于：

mx≡nmodpm^x\equiv n \mod p

我们令 $x=a\lceil \sqrt{p} \rceil - b \ (a,b\in [0,\lceil \sqrt{p} \rceil])$，原式就能转化为：

ma⌈p⌉≡nmbmodpm^{a\lceil \sqrt{p} \rceil}\equiv nm^b \mod p

这时分别枚举 $b,a$，第一遍枚举用一个 map 记录，第二遍枚举看是否存在，复杂度应该是 $O(n\log n)$ 的。

代码：

C++
#include<bits/stdc++.h>
using namespace std;
#define int long long

int qpow(int x,int y,int p){
    int res=1;
    while(y){
        if(y&1) (res*=x)%=p;
        (x*=x)%=p,y>>=1;
    }
    return res;
}

int BSGS(int p,int m,int n){
    map<int,int> mp;
    int gp=ceil(sqrt(p));
    for(int b=0;b<=gp;b++) mp[n*qpow(m,b,p)%p]=b;
    for(int a=0;a<=gp;a++){
        int val=qpow(m,a*gp,p);
        if(mp.find(val)!=mp.end()){
            int b=mp[val];
            if(a*gp-b>=0) return a*gp-b;
        }
    }
    return -1;
}

signed main(){
    int n,b,p;
    cin>>p>>b>>n;
    int ans=BSGS(p,b,n);
    if(ans==-1) cout<<"no solution";
    else cout<<ans;
    return 0;
}

AT_arc084_b [ABC077D] Small Multiple

同余最短路。

考虑在模 $K$ 的意义下建图。在 $i$ 与 $i+1$ 之间建一条边权为 $1$ 的边，表示数位和加了 $1$；在 $i$ 与 $10i$ 之间建一条边权为 $0$ 的边，表示数位和没有变化，这样图中的点就能代表所有数了，从 $1$ 到 $0$ 跑一遍最短路即可（不要忘记加上 $1$ 的贡献）。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int k;
int dis[N];
struct node{
    int v,w;
    bool operator<(const node b)const{
        return w>b.w;
    }
};
vector<node> g[N];

void dj(){
    priority_queue<node> q;
    memset(dis,0x3f,sizeof dis);
    dis[1]=1;
    q.push({1,1});
    while(q.size()){
        auto[u,d]=q.top();
        q.pop();
        for(auto[v,w]:g[u]){
            if(d+w<dis[v]){
                dis[v]=d+w;
                q.push({v,dis[v]});
            }
        }
    }
}

signed main(){
    cin>>k;
    for(int i=0;i<k;i++){
        g[i].push_back({(i+1)%k,1});
        g[i].push_back({(i*10)%k,0});
    }
    dj();
    cout<<dis[0];
    return 0;
}

P3232 [HNOI2013 / JSOI2013] 游走

设 $f_i$ 表示经过点 $i$ 的期望次数，那么对于一条边 $E_i=(u,v)$，经过边的期望次数就是 $\frac{f_u}{d_u}+\frac{f_v}{d_v}$。

可以列出方程：

{f1+(−1d2f2)+...+(−1dn−1fn−1)=1(−1d1f1)+f2+...+(−1dn−1fn−1)=0…(−1d1f1)+(−1d2f2)+...+fn−1=0\begin{cases} f_1+(-\frac{1}{d_2}f_2)+...+(-\frac{1}{d_{n-1}}f_{n-1})=1 \\ (-\frac{1}{d_1}f_1)+f2+...+(-\frac{1}{d_{n-1}}f_{n-1})=0 \\ \dots \\ (-\frac{1}{d_1}f_1)+(-\frac{1}{d_2}f_2)+...+f_{n-1}=0 \\ \end{cases}

高斯消元即可。

最后贪心地给期望经过次数高的边赋小的值即可。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

const int N=505,M=125005;
const double eps=1e-5;
int n,m;
int u[M],v[M],d[M];
double a[N][N],g[M],f[N],ans;

void guass(){
    int r=1;
	for(int i=1;i<n;i++){
		int h=r;
		for(int j=r+1;j<n;j++) if(fabs(a[j][i])>fabs(a[h][i])) h=j;
		if(fabs(a[h][i])<eps) continue;
		swap(a[r],a[h]);
        double x=a[r][i];
		for(int j=i;j<=n;j++) a[r][j]/=x;
		for(int j=r+1;j<n;j++){
			double x=a[j][i];
			for(int k=i;k<=n;k++) a[j][k]-=a[r][k]*x;
		}
		r++;
	}
    for(int i=n-1;i>=1;i--){
		f[i]=a[i][n];
		for(int j=i+1;j<n;j++) f[i]-=a[i][j]*f[j];
	}
}

signed main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",u+i,v+i);
        d[u[i]]++,d[v[i]]++;
    }
    a[1][n]=1;
    for(int i=1;i<n;i++) a[i][i]=1;
    for(int i=1;i<=m;i++){
        if(v[i]<n) a[u[i]][v[i]]=-1.0/d[v[i]];
        if(u[i]<n) a[v[i]][u[i]]=-1.0/d[u[i]];
    }
    guass();
    for(int i=1;i<=m;i++) g[i]=f[u[i]]/d[u[i]]+f[v[i]]/d[v[i]];
    sort(g+1,g+1+m);
    for(int i=1;i<=m;i++) ans+=(m-i+1)*g[i];
    printf("%0.3f",ans);
    return 0;
}

P7112 【模板】行列式求值

把矩阵变成上三角矩阵，之后主对角线上数字之积就是答案。

不知道原理。

注意这是取模意义下的，所以用到了辗转相除高斯消元法，原理就是辗转相除法。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=605;
int n,p;
int a[N][N];

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>p;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j],a[i][j]%=p;
    int f=1;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            while(a[j][i]){
                int t=a[i][i]/a[j][i];
                for(int k=i;k<=n;k++) a[i][k]=(a[i][k]-t*a[j][k]%p+p)%p;
                swap(a[i],a[j]);
                f=-f;
            }
        }
    }
    int ans=1;
    for(int i=1;i<=n;i++) ans=ans*a[i][i]%p;
    ans=(ans*f%p+p)%p;
    cout<<ans<<"\n";
    return 0;
}

P4151 [WC2011] 最大 XOR 和路径

不难发现，环上的权值是能够完整地取得的，而从 $1$ 到 $n$ 的链是必取的，所以我们把环上的异或和放在线性基里，最后用 $1$ 到 $n$ 的链去查询即可。

这里要注意位运算的优先级，为了保险，还是多打一点括号比较好。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=5e4+5;
int n,m;
int dis[N],tag[N];
struct node{
    int v,w;
};
vector<node> g[N];

struct BASIS{
    int a[70];
    void insert(int x){
        for(int i=63;i>=0;i--){
            if(((x>>i)&1)==0) continue;
            if(!a[i]){
                a[i]=x;
                return;
            }
            x^=a[i];
        }
    }
    int check(int k){
        for(int i=63;i>=0;i--) if((k^a[i])>k) k^=a[i];
        return k;
    }
}basis;

void dfs(int u){
    tag[u]=1;
    for(auto[v,w]:g[u]){
        if(!tag[v]){
            dis[v]=dis[u]^w,tag[v]=1;
            dfs(v);
        }
        else basis.insert(dis[u]^dis[v]^w);
    }
}

signed main(){
    cin>>n>>m;
    for(int i=1,u,v,w;i<=m;i++){
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    dfs(1);
    cout<<basis.check(dis[n]);
    return 0;
}

P4869 albus就是要第一个出场

可以感性证明一下线性基所能构造出的所有数中，所有数都重复出现了 $2^{n-k}$ 次。其中 $k$ 表示线性基的大小。

可以感性理解一下，枚举除线性基外的子集，若想子集异或和异或上线性基构成的一个数都为同一个数，至于要线性基内异或出子集异或和再异或上需要构造的数即可，根据线性基的定义可知这是一定能做到的，因此得证。

这样我们就先拆分查询的数的二进制，求出它在不重复的情况下的排名，之后再计算重复值的贡献即可。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int mod=10086;
int n,x,q,idx,rk;
int k[70];

struct BASIS{
    int a[70];
    void insert(int x){
        for(int i=63;i>=0;i--){
            if(((x>>i)&1)==0) continue;
            if(!a[i]){
                a[i]=x;
                return;
            }
            x^=a[i];
        }
    }
}basis;

int qpow(int x,int y){
    int res=1;
    while(y){
        if(y&1) (res*=x)%=mod;
        (x*=x)%=mod,y>>=1;
    }
    return res;
}

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        basis.insert(x);
    }
    cin>>q;
    for(int i=0;i<63;i++) if(basis.a[i]) k[idx++]=i;
    for(int i=0;i<idx;i++) if((q>>k[i])&1) rk+=(1<<i);
    cout<<((qpow(2,n-idx)*rk)%mod+1)%mod;
    return 0;
}

P11620 [Ynoi Easy Round 2025] TEST_34

超级线段树+树状数组+线性基题，考虑求出 $a$ 的异或差分数组 $b$，这样就能把区间修改转化为单点修改。

不难想到，$a_l,...,a_r$ 的线性基与 $a_l,b_{l+1},...,b_r$ 的线性基是一致的，所以我们用线段树维护区间线性基，用树状数组维护区间异或前缀和即可。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define lc p<<1
#define rc p<<1|1
const int N=5e4+5;
int n,m;
int a[N],b[N];

struct BASIS{
    int a[40];
    void clear(){
        memset(a,0,sizeof a);
    }
    void insert(int x){
        for(int i=31;i>=0;i--){
            if(((x>>i)&1)==0) continue;
            if(!a[i]){
                a[i]=x;
                return;
            }
            x^=a[i];
        }
    }
    void merge(BASIS x){
        for(int i=31;i>=0;i--) 
            if(x.a[i]) insert(x.a[i]);
    }
    int check(int x){
        for(int i=31;i>=0;i--) if((x^a[i])>x) x^=a[i];
        return x;
    }
};

struct BIT{
    int t[N];
    void add(int x,int k){
        for(;x<N;x+=x&-x) t[x]^=k;
    }
    int get(int x){
        int res=0;
        for(;x>0;x-=x&-x) res^=t[x];
        return res;
    }
}bit;

struct SEG{    
    BASIS tr[N<<2];
    void pushup(int p){
        tr[p]=tr[lc];
        tr[p].merge(tr[rc]);
    }
    void build(int p,int l,int r){
        if(l==r){
            tr[p].insert(b[l]);
            return;
        }
        int mid=(l+r)>>1;
        build(lc,l,mid);
        build(rc,mid+1,r);
        pushup(p);
    }
    void change(int p,int l,int r,int x,int k){
        if(l==r){
            tr[p].clear();
            tr[p].insert(k);
            return;
        }
        int mid=(l+r)>>1;
        if(x<=mid) change(lc,l,mid,x,k);
        else change(rc,mid+1,r,x,k);
        pushup(p);
    }
    BASIS get(int p,int l,int r,int x,int y){
        if(l>=x&&r<=y) return tr[p];
        int mid=(l+r)>>1;
        BASIS res;
        res.clear();
        if(x<=mid) res.merge(get(lc,l,mid,x,y));
        if(y>mid) res.merge(get(rc,mid+1,r,x,y));
        return res;
    }
}seg;

signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i]^a[i-1],bit.add(i,b[i]);
    seg.build(1,1,n);
    for(int i=1;i<=m;i++){
        int op,l,r,v;
        cin>>op>>l>>r>>v;
        if(op==1){
            bit.add(l,v),b[l]^=v;
            if(r<n) bit.add(r+1,v),b[r+1]^=v;
            seg.change(1,1,n,l,b[l]);
            if(r<n) seg.change(1,1,n,r+1,b[r+1]);
        }
        else{
            BASIS ans;
            if(r>l) ans=seg.get(1,1,n,l+1,r);
            else ans.clear();
            ans.insert(bit.get(l));
            cout<<ans.check(v)<<"\n";
        }
    }
    return 0;
}