9.27 近期比赛总结

ooliver 发布于 14 小时前 51 次阅读 OI

AI 摘要

我最近三场正睿 OI，三道题三个性质：区间 2 的奇偶配线段树，gcd 种类不超 log，环上最近点对化计数容斥。代码长，思路一戳就破，尤其调和级数，妙到想重写。

26 CSP 七连测 day4 | 正睿 OI

题目 #3649 | 正睿 OI

尝试找一些性质，如果区间内 $2$ 的数量为奇数，考虑将最后一个 $2$ 移动到最后，其余两两配对，移动到一起；如果区间内 $2$ 的个数为偶数，那考虑直接两两配对或者将最后一个放到最后，并且在其余的 $2$ 中找一个跳过。

这个东西用线段树乱搞一下即可。

代码：

C++
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lc p<<1
#define rc p<<1|1

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[N<<2];

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;i<2;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&&r<=y) return tr[p];
    int mid=(l+r)>>1;
    if(y<=mid) 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;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(m--){
        int l,r;
        cin>>l>>r;
        int ans=get(l,r);
        cout<<ans<<"\n";
    }
    return 0;
}

题目 #3651 | 正睿 OI

一个性质：以某个数结尾的区间的 $gcd$ 数量不会超过 $\log m$，知道这个性质后直接枚举瞎搞就行了。

代码：

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

#define int long long
const int N=2e5+5;
int n,m,a[N],pre[N],suf[N],tot;
vector<pair<int,int>> l[N],r[N];

vector<int> getp(int x){
    vector<int> p;
    for(int i=2;i*i<=x;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;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;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;i<=n;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;
        vector<int> 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<=m) c.push_back(p*q);
        vector<pair<int,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));
    }
    cout<<ans<<"\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<bits/stdc++.h>
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<=n;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(r<0||r>n) return 0;
    return fac[n]*ifac[r]%mod*ifac[n-r]%mod;
}

void getpw(int lim,int k,vector<int>& pw){
    pw.assign(lim+1,0);
    vector<int> pr;
    vector<bool> vis(lim+1,0);
    pw[1]=1;
    for(int i=2;i<=lim;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;
    vector<int> pw;
    getpw(mz,k,pw);
    vector<int> de(mz+1,0);
    for(int z=1;z<=mz;z++) de[z]=(pw[z]-pw[z-1]+mod)%mod;
    for(int n=1;n<m;n++){
        int s=0,lz=m/(n+1);
        for(int z=1;z<=lz;z++) s=(s+de[z]*C(m-(n+1)*z+n,n))%mod;
        cout<<s*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;
}