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

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 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 我们令 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 记录，第二遍枚举看是否存在。代码： 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 同余最短路。考虑在模 K 的意义下建图。在 i 与 i+1 之间建一条边权为 1 的边，表示数位和加了 1；在 i 与 10i 之间建一条边权为 0 的边，表示数位和没有变化，这样图中的点就能代表所有数了，从 1 到 0 跑一遍最短路即可（不要忘记加上 1 的贡献）。代码： 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] 游走设 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 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 【模板】行列式求值把矩阵变成上三角矩阵，之后主对角线上数字之积就是答案。不知道原理。注意这是取模意义下的，所以用到了辗转相除高斯消元法，原理就是辗转相除法。复杂度可以证明是 O(n^2(n+\log n)) 的。代码： 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 和路径不难发现，环上的权值是能够完整地取得的，而从 1 到 n 的链是必取的，所以我们把环上的异或和放在线性基里，最后用 1 到 n 的链去查询即可。这里要注意位运算的优先级，为了保险，还是多打一点括号比较好。代码： 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就是要第一个出场可以感性证明一下线性基所能构…