26 CSP 七连测 day4 | 正睿 OI 题目 #3649 | 正睿 OI 尝试找一些性质，如果区间内 2 的数量为奇数，考虑将最后一个 2 移动到最后，其余两两配对，移动到一起；如果区间内 2 的个数为偶数，那考虑直接两两配对或者将最后一个放到最后，并且在其余的 2 中找一个跳过。 这个东西用线段树乱搞一下即可。 代码： C++ #include using namespace std; #define int long long #define lc p=inf/2?inf:x.mn[i]+cost1(y,i^p)); int v2=(y.mn[i^p]>=inf/2?inf:cost0(x,i)+y.mn[i^p]); res.mn[i]=min(v1,v2); } return res; } void build(int p,int l,int r){ if(l==r){ if(a[l]==2) tr[p]={1,l,0,{0,inf}}; else tr[p]={0,0,0,{inf,inf}}; return; } int mid=(l+r)>>1; build(lc,l,mid); build(rc,mid+1,r); tr[p]=merge(tr[lc],tr[rc]); } tree query(int p,int l,int r,int x,int y){ if(l>=x&&r>1; if(ymid) return query(rc,mid+1,r,x,y); return merge(query(lc,l,mid,x,y),query(rc,mid+1,r,x,y)); } int get(int l,int r){ tree ans=query(1,1,n,l,r); if(!ans.cnt) return 0; if(ans.cnt&1){ ans.sum0+=r+1,ans.cnt++; return (ans.sum0-ans.sum1)-(ans.cnt>>1); } int ans1=(ans.sum0-ans.sum1)-(ans.cnt>>1); int ans2=ans.mn[0]+r-(ans.cnt>>1)+1; return min(ans1,ans2); } signed main(){ freopen("xtw.in","r",stdin); freopen("xtw.out","w",stdout); ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>m; for(int i=1;i>a[i]; build(1,1,n); while(m--){ int l,r; cin>>l>>r; int ans=get(l,r); cout `#include using namespace std; #define int long long #define lc p #define rc p const int N=2e5+5; const int inf=1e16; int n,m; int a[N]; struct tree{ int cnt,sum1,sum0; int mn[2]; }tr[N2]; inline int cost0(const tree &t,int par){ return par?(t.sum1-t.sum0):(t.sum0-t.sum1); } inline int cost1(const tree &t,int par){ return par?(t.sum0-t.sum1):(t.sum1-t.sum0); } tree merge(tree x,tree y){ tree res; res.cnt=x.cnt+y.cnt; if(x.cnt&1) res.sum1=x.sum1+y.sum0,res.sum0=x.sum0+y.sum1; else res.sum1=x.sum1+y.sum1,res.sum0=x.sum0+y.sum0; int p=x.cnt&1; for(int i=0;i2;i++){ int v1=(x.mn[i]>=inf/2?inf:x.mn[i]+cost1(y,i^p)); int v2=(y.mn[i^p]>=inf/2?inf:cost0(x,i)+y.mn[i^p]); res.mn[i]=min(v1,v2); } return res; } void build(int p,int l,int r){ if(l==r){ if(a[l]==2) tr[p]={1,l,0,{0,inf}}; else tr[p]={0,0,0,{inf,inf}}; return; } int mid=(l+r)>>1; build(lc,l,mid); build(rc,mid+1,r); tr[p]=merge(tr[lc],tr[rc]); } tree query(int p,int l,int r,int x,int y){ if(l>=x&&ry) return tr[p]; int mid=(l+r)>>1; if(ymid) return query(lc,l,mid,x,y); if(x>mid) return query(rc,mid+1,r,x,y); return merge(query(lc,l,mid,x,y),query(rc,mid+1,r,x,y)); } int get(int l,int r){ tree ans=query(1,1,n,l,r); if(!ans.cnt) return 0; if(ans.cnt&1){ ans.sum0+=r+1,ans.cnt++; return (ans.sum0-ans.sum1)-(ans.cnt>>1); } int ans1=(ans.sum0-ans.sum1)-(ans.cnt>>1); int ans2=ans.mn[0]+r-(ans.cnt>>1)+1; return min(ans1,ans2); } signed main(){ freopen("xtw.in","r",stdin); freopen("xtw.out","w",stdout); ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>m; for(int i=1;in;i++) cin>>a[i]; build(1,1,n); while(m--){ int l,r; cin>>l>>r; int ans=get(l,r); coutans"\n"; } return 0; }` 题目 #3651 | 正睿 OI 一个性质：以某个数结尾的区间的 gcd 数量不会超过 \log m，知道这个性质后直接枚举瞎搞就行了。 代码： C++ #include using namespace std; #define int long long const int N=2e5+5; int n,m,a[N],pre[N],suf[N],tot; vector> l[N],r[N]; vector getp(int x){ vector p; for(int i=2;i*i1) p.push_back(x); return p; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>m; for(int i=1;i>a[i]; for(int i=1;i1) pre[i]+=p.second; tot+=pre[i],pre[i]+=pre[i-1]; } for(int i=n;i>=1;i--){ r[i].push_back({a[i],1}); for(auto p:r[i+1]){ int g=__gcd(p.first,a[i]); if(g==r[i].back().first) r[i].back().second+=p.second; else r[i].push_back({g,p.second}); } for(auto p:r[i]) if(p.first>1) suf[i]+=p.second; suf[i]+=suf[i+1]; } int ans=tot; for(int i=1;i1) gl=p.first; for(auto p:r[i+1]) if(p.first>1) gr=p.first; vector pl=getp(gl),pr=getp(gr),c={a[i],2}; for(int p:pl) c.push_back(p); for(int q:pr) c.push_back(q); for(int p:pl) for(int q:pr) if(p*q> sl=l[i-1],sr=r[i+1]; sl.push_back({0,1}); sr.push_back({0,1}); int best=0; for(int w:c){ int cur=0; for(auto x:sl){ int g=__gcd(x.first,w); if(g==1&&x.first) continue; for(auto y:sr) if(__gcd(g,y.first)>1) cur+=x.second*y.second; } best=max(best,cur); } int mid=tot-pre[i-1]-suf[i+1]; ans=max(ans,tot+max(0ll,best-mid)); } cout `#include using namespace std; #define int long long const int N=2e5+5; int n,m,a[N],pre[N],suf[N],tot; vectorpairint,int>> l[N],r[N]; vectorint> getp(int x){ vectorint> p; for(int i=2;i*ix;i++){ if(x%i==0){ p.push_back(i); while(x%i==0) x/=i; } } if(x>1) p.push_back(x); return p; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>m; for(int i=1;in;i++) cin>>a[i]; for(int i=1;in;i++){ l[i].push_back({a[i],1}); for(auto p:l[i-1]){ int g=__gcd(p.first,a[i]); if(g==l[i].back().first) l[i].back().second+=p.second; else l[i].push_back({g,p.second}); } for(auto p:l[i]) if(p.first>1) pre[i]+=p.second; tot+=pre[i],pre[i]+=pre[i-1]; } for(int i=n;i>=1;i--){ r[i].push_back({a[i],1}); for(auto p:r[i+1]){ int g=__gcd(p.first,a[i]); if(g==r[i].back().first) r[i].back().second+=p.second; else r[i].push_back({g,p.second}); } for(auto p:r[i]) if(p.first>1) suf[i]+=p.second; suf[i]+=suf[i+1]; } int ans=tot; for(int i=1;in;i++){ int gl=0,gr=0; for(auto p:l[i-1]) if(p.first>1) gl=p.first; for(auto p:r[i+1]) if(p.first>1) gr=p.first; vectorint> pl=getp(gl),pr=getp(gr),c={a[i],2}; for(int p:pl) c.push_back(p); for(int q:pr) c.push_back(q); for(int p:pl) for(int q:pr) if(p*qm) c.push_back(p*q); vectorpairint,int>> sl=l[i-1],sr=r[i+1]; sl.push_back({0,1}); sr.push_back({0,1}); int best=0; for(int w:c){ int cur=0; for(auto x:sl){ int g=__gcd(x.first,w); if(g==1&&x.first) continue; for(auto y:sr) if(__gcd(g,y.first)>1) cur+=x.second*y.second; } best=max(best,cur); } int mid=tot-pre[i-1]-suf[i+1]; ans=max(ans,tot+max(0ll,best-mid)); } coutans"\n"; return 0; }` 题目 #3652 | 正睿 OI 数学题，其实很简单。 对于一个数组 a，其子数组 a[l,r] 的价值应该就是 min((suma_r-suma_{l-1})\mod m,(suma_{l-1}-suma_{r})\mod m+m)。考虑把 suma 看成长度为 m 的环上的点，那答案就是环上最近点对的 k 次方。 考虑枚举这个最近点对的距离，就变成了计数题，即环上每个点对距离都大于或等于枚举的这个距离，再容斥一下就可以了，复杂度是调和级数。 代码： C++ #include using namespace std; #define int long long const int N=2e6+5,mod=998244353; int m,k,fac[N],ifac[N]; int qpow(int a,int b){ int r=1; while(b){ if(b&1) r=r*a%mod; a=a*a%mod; b>>=1; } return r; } void init(int n){ fac[0]=1; for(int i=1;i=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod; } int C(int n,int r){ if(rn) return 0; return fac[n]*ifac[r]%mod*ifac[n-r]%mod; } void getpw(int lim,int k,vector& pw){ pw.assign(lim+1,0); vector pr; vector vis(lim+1,0); pw[1]=1; for(int i=2;ilim) break; vis[i*p]=1; pw[i*p]=pw[i]*pw[p]%mod; if(i%p==0) break; } } } void solve(){ cin>>m>>k; int mz=m/2; vector pw; getpw(mz,k,pw); vector de(mz+1,0); for(int z=1;z>T; while(T--) solve(); return 0; } `#include using namespace std; #define int long long const int N=2e6+5,mod=998244353; int m,k,fac[N],ifac[N]; int qpow(int a,int b){ int r=1; while(b){ if(b&1) r=r*a%mod; a=a*a%mod; b>>=1; } return r; } void init(int n){ fac[0]=1; for(int i=1;in;i++) fac[i]=fac[i-1]*i%mod; ifac[n]=qpow(fac[n],mod-2); for(int i=n-1;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod; } int C(int n,int r){ if(r0||r>n) return 0; return fac[n]*ifac[r]%mod*ifac[n-r]%mod; } void getpw(int lim,int k,vectorint>& pw){ pw.assign(lim+1,0); vectorint> pr; vectorbool> vis(lim+1,0); pw[1]=1; for(int i=2;ilim;i++){ if(!vis[i]){ pr.push_back(i); pw[i]=qpow(i,k); } for(int p:pr){ if(i*p>lim) break; vis[i*p]=1; pw[i*p]=pw[i]*pw[p]%mod; if(i%p==0) break; } } } void solve(){ cin>>m>>k; int mz=m/2; vectorint> pw; getpw(mz,k,pw); vectorint> de(mz+1,0); for(int z=1;zmz;z++) de[z]=(pw[z]-pw[z-1]+mod)%mod; for(int n=1;nm;n++){ int s=0,lz=m/(n+1); for(int z=1;zlz;z++) s=(s+de[z]*C(m-(n+1)*z+n,n))%mod; couts*fac[n]%mod" \n"[n==m-1]; } } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); init(N-1); int T; cin>>T; while(T--) solve(); return 0; }`
9.27 近期比赛总结
笔记