ZR 集训 Day13 - 同余、线代入门
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 把 数组算出来，在算它的逆元，之后就是 EXCRT 的模板了。
代码：
C++
#include
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 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>a[i];
for(int i=1;i>p[i];
for(int i=1;i>awd[i];
s.clear();
for(int i=1;i>x;
s.insert(x);
}
for(int i=1;i>T;
while(T--) solve();
return 0;
}
`#include
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];
multisetint> 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;in;i++) cin>>a[i];
for(int i=1;in;i++) cin>>p[i];
for(int i=1;in;i++) cin>>awd[i];
s.clear();
for(int i=1;im;i++){
int x;cin>>x;
s.insert(x);
}
for(int i=1;in;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;in;i++) mx=max(mx,(a[i]+atk[i]-1)/atk[i]);
int b1=0,m1=1;
for(int i=1;in;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(k10) k1+=step;
b1=b1+(i128)k1*m1;
m1=m1/g*mi;
b1=(b1%m1+m1)%m1;
}
int ans=b1;
if(ansmx) ans+=(mx-ans+m1-1)/m1*m1;
coutans"\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
我们令 ，原式就能转化为：
ma⌈p⌉≡nmbmodpm^{a\lceil \sqrt{p} \rceil}\equiv nm^b \mod p
这时分别枚举 ，第一遍枚举用一个 map 记录，第二遍枚举看是否存在。
代码：
C++
#include
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 mp;
int gp=ceil(sqrt(p));
for(int b=0;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
`#include
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){
mapint,int> mp;
int gp=ceil(sqrt(p));
for(int b=0;bgp;b++) mp[n*qpow(m,b,p)%p]=b;
for(int a=0;agp;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 coutans;
return 0;
}`
AT_arc084_b [ABC077D] Small Multiple
同余最短路。
考虑在模 的意义下建图。在 与 之间建一条边权为 的边，表示数位和加了 ；在 与 之间建一条边权为 的边，表示数位和没有变化，这样图中的点就能代表所有数了，从 到 跑一遍最短路即可（不要忘记加上 的贡献）。
代码：
C++
#include
using namespace std;
const int N=1e5+5;
int k;
int dis[N];
struct node{
int v,w;
bool operatorb.w;
}
};
vector g[N];
void dj(){
priority_queue 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>k;
for(int i=0;i
`#include
using namespace std;
const int N=1e5+5;
int k;
int dis[N];
struct node{
int v,w;
bool operatorconst node b)const{
return w>b.w;
}
};
vectornode> g[N];
void dj(){
priority_queuenode> 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+wdis[v]){
dis[v]=d+w;
q.push({v,dis[v]});
}
}
}
}
signed main(){
cin>>k;
for(int i=0;ik;i++){
g[i].push_back({(i+1)%k,1});
g[i].push_back({(i*10)%k,0});
}
dj();
coutdis[0];
return 0;
}`
P3232 [HNOI2013 / JSOI2013] 游走
设 表示经过点 的期望次数，那么对于一条边 ，经过边的期望次数就是 。
可以列出方程：
{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
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;ifabs(a[h][i])) h=j;
if(fabs(a[h][i])=1;i--){
f[i]=a[i][n];
for(int j=i+1;j
`#include
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;in;i++){
int h=r;
for(int j=r+1;jn;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;jn;j++) a[r][j]/=x;
for(int j=r+1;jn;j++){
double x=a[j][i];
for(int k=i;kn;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;jn;j++) f[i]-=a[i][j]*f[j];
}
}
signed main(){
scanf("%d%d",&n,&m);
for(int i=1;im;i++){
scanf("%d%d",u+i,v+i);
d[u[i]]++,d[v[i]]++;
}
a[1][n]=1;
for(int i=1;in;i++) a[i][i]=1;
for(int i=1;im;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;im;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;im;i++) ans+=(m-i+1)*g[i];
printf("%0.3f",ans);
return 0;
}`
P7112 【模板】行列式求值
把矩阵变成上三角矩阵，之后主对角线上数字之积就是答案。
不知道原理。
注意这是取模意义下的，所以用到了辗转相除高斯消元法，原理就是辗转相除法。
复杂度可以证明是 的。
代码：
C++
#include
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>a[i][j],a[i][j]%=p;
int f=1;
for(int i=1;i
`#include
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;in;i++) for(int j=1;jn;j++) cin>>a[i][j],a[i][j]%=p;
int f=1;
for(int i=1;in;i++){
for(int j=i+1;jn;j++){
while(a[j][i]){
int t=a[i][i]/a[j][i];
for(int k=i;kn;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;in;i++) ans=ans*a[i][i]%p;
ans=(ans*f%p+p)%p;
coutans"\n";
return 0;
}`
P4151 [WC2011] 最大 XOR 和路径
不难发现，环上的权值是能够完整地取得的，而从 到 的链是必取的，所以我们把环上的异或和放在线性基里，最后用 到 的链去查询即可。
这里要注意位运算的优先级，为了保险，还是多打一点括号比较好。
代码：
C++
#include
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 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>u>>v>>w;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
dfs(1);
cout
`#include
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;
};
vectornode> 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;im;i++){
cin>>u>>v>>w;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
dfs(1);
coutbasis.check(dis[n]);
return 0;
}`
P4869 albus就是要第一个出场
可以感性证明一下线性基所能构造出的所有数中，所有数都重复出现了 次。其中 表示线性基的大小。
可以感性理解一下，枚举除线性基外的子集，若想子集异或和异或上线性基构成的一个数都为同一个数，至于要线性基内异或出子集异或和再异或上需要构造的数即可，根据线性基的定义可知这是一定能做到的，因此得证。
这样我们就先拆分查询的数的二进制，求出它在不重复的情况下的排名，之后再计算重复值的贡献即可。
代码：
C++
#include
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>x;
basis.insert(x);
}
cin>>q;
for(int i=0;i>k[i])&1) rk+=(1
`#include
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;in;i++){
cin>>x;
basis.insert(x);
}
cin>>q;
for(int i=0;i63;i++) if(basis.a[i]) k[idx++]=i;
for(int i=0;iidx;i++) if((q>>k[i])&1) rk+=(1i);
cout((qpow(2,n-idx)*rk)%mod+1)%mod;
return 0;
}`
P11620 [Ynoi Easy Round 2025] TEST_34
超级线段树+树状数组+线性基题，考虑求出 的异或差分数组 ，这样就能把区间修改转化为单点修改。
不难想到， 的线性基与 的线性基是一致的，所以我们用线段树维护区间线性基，用树状数组维护区间异或前缀和即可。
代码：
C++
#include
using namespace std;
#define int long long
#define lc p=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(;x0;x-=x&-x) res^=t[x];
return res;
}
}bit;
struct SEG{
BASIS tr[N>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=x&&r>1;
BASIS res;
res.clear();
if(xmid) res.merge(get(rc,mid+1,r,x,y));
return res;
}
}seg;
signed main(){
cin>>n>>m;
for(int i=1;i>a[i],b[i]=a[i]^a[i-1],bit.add(i,b[i]);
seg.build(1,1,n);
for(int i=1;i>op>>l>>r>>v;
if(op==1){
bit.add(l,v),b[l]^=v;
if(rl) ans=seg.get(1,1,n,l+1,r);
else ans.clear();
ans.insert(bit.get(l));
cout
`#include
using namespace std;
#define int long long
#define lc p
#define rc p
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(;xN;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[N2];
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(xmid) 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&&ry) return tr[p];
int mid=(l+r)>>1;
BASIS res;
res.clear();
if(xmid) 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;in;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;im;i++){
int op,l,r,v;
cin>>op>>l>>r>>v;
if(op==1){
bit.add(l,v),b[l]^=v;
if(rn) bit.add(r+1,v),b[r+1]^=v;
seg.change(1,1,n,l,b[l]);
if(rn) 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));
coutans.check(v)"\n";
}
}
return 0;
}`