[ICPC 2019 Nanchang Invitational Online G]tsy’s number

这几周很忙…好久没有静心做点题了。。
北理校赛的期望DP题做不对
南昌网赛的积性函数题不会做
各种专题都有待加强
这几天先再看看数论吧。

Link

Solution

首先

\begin{aligned}
&\frac{\varphi(i)\varphi(j^2)\varphi(k^3)}{\varphi(i)\varphi(j)\varphi(k)}\\
=&\frac {j^2\prod_{p|j^2}(1-\frac 1p)k^3\prod_{p|k^3}(1-\frac 1p)}
{j\prod_{p|j}(1-\frac 1p)k\prod_{p|k}(1-\frac 1p)}\\
=&jk^2
\end{aligned}

式子化为

\begin{aligned}
&\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^njk^2\varphi((i,j,k))\\
=&\sum_{d}\varphi(d)\sum_{i=1}^{[\frac nd]}\sum_{j=1}^{[\frac nd]}\sum_{k=1}^{[\frac nd]}
(jd)(kd)^2[(i,j,k)=1]\\
=&\sum_{d}d^3\varphi(d)\sum_{i=1}^{[\frac nd]}\sum_{j=1}^{[\frac nd]}\sum_{k=1}^{[\frac nd]}
jk^2[(i,j,k)=1]\\
=&\sum_{d}d^3\varphi(d)\sum_{i=1}^{[\frac nd]}\sum_{j=1}^{[\frac nd]}\sum_{k=1}^{[\frac nd]}
jk^2\sum_{t|i,t|j,t|k}\mu(t)\\
=&\sum_{d}d^3\varphi(d)\sum_{t}t^3\mu(t)\sum_{i=1}^{[\frac n{dt}]}\sum_{j=1}^{[\frac n{dt}]}\sum_{k=1}^{[\frac n{dt}]}jk^2\\
=&\sum_{T}T^3\sum_{d|T}\varphi(d)\mu(\frac Td)\sum_{i=1}^{[\frac nT]}\sum_{j=1}^{[\frac nT]}\sum_{k=1}^{[\frac nT]}jk^2\\
=&\sum_{T}T^3\sum_{d|T}\varphi(d)\mu(\frac Td)[\frac nT](\sum_{j=1}^{[\frac nT]}j)(\sum_{k=1}^{[\frac nT]}k^2)
\end{aligned}

考虑筛出T^3(\varphi*\mu)(T)的前缀和。
都是积性函数,随便筛的。

\begin{aligned}
&(p^t)^3(\mu * \varphi)(p^t)\\
=&p^{3t}\sum_{d|p^t}\mu(d)\varphi(\frac {p^t}d)\\
=&p^{3t}(\mu(1)\varphi(p^t)+\mu(p)\varphi(p^{t-1}))\\
=&p^{3t}(\varphi(p^t)-\varphi(p^{t-1}))\\
\end{aligned}

Code

线性筛也写的不熟,写一次忘一次。

#include <bits/stdc++.h>

const int N=1e7,XN=N+11;

unsigned int Sum(unsigned int x) {
    return (long long)x*(x+1)/2;
}

unsigned int Sum2(unsigned int x) {
    return (unsigned long long)x*(x+1)%(6ull<<30)*(2*x+1)%(6ull<<30)/6;
}

unsigned int Pow3(unsigned int x) {
    return x*x*x;
}

unsigned int g[XN];
void Prep() {
    static bool notPrime[XN];
    static struct { int p,pt; }mp[XN];
    static int prime[XN],pcnt;

    g[1]=1;

    for(int i=2;i<=N;++i) {
        if(!notPrime[i]) {
            prime[++pcnt]=i;
            mp[i]={i,i};
            g[i]=Pow3(i)*(i-2);
        }
        for(int j=1,x;j<=pcnt && prime[j]<=mp[i].p && (x=i*prime[j])<=N;++j) {
            notPrime[x]=1;
            if(mp[i].p==prime[j])
                mp[x]={prime[j],mp[i].pt*prime[j]};
            else
                mp[x]={prime[j],prime[j]};
            auto Phi=[&](int pt)->int {
                return pt==1?1:(mp[x].p-1)*(pt/mp[x].p);
            };
            g[x]=g[x/mp[x].pt]*Pow3(mp[x].pt)*(Phi(mp[x].pt)-Phi(mp[x].pt/mp[x].p));
        }
    }
    for(int i=1;i<=N;++i)
        g[i]+=g[i-1];
}

void Work() {
    int n;std::cin>>n;
    unsigned int Ans=0;
    for(int l=1,r;l<=n;l=r+1) {
        r=n/(n/l);
        Ans+=(n/l)*Sum(n/l)*Sum2(n/l)*(g[r]-g[l-1]);
    }
    std::cout<<(Ans%(1<<30))<<'\n';
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    //freopen("input","r",stdin);
    Prep();
    /*
    for(int i=1;i<=100;++i)
        std::cerr<<Sum(i)-Sum(i-1)<<' '<<Sum2(i)-Sum2(i-1)<<'\n';
    */
    int T;std::cin>>T;
    while(T--)
        Work();
    return 0;
}

[ICPC 2017 ECNA B]Craters

Link

Solution

求出所有可能在凸包上的切线,然后半平面交。。。
二维量的eps比较微妙

Code

const int XN=1e5+11;
const double eps=1e-4,inf=1e100,pi=acos(-1);

int sgn(double const &x) {
    return (x>-eps)-(x<eps);
}

struct Point {
    double x,y;

    double Length() const {
        return sqrt(x*x+y*y);
    }

    double Length2() const {
        return x*x+y*y;
    }

    Point Unit() const {
        double len=sqrt(x*x+y*y);
        return {x/len,y/len};
    }

    Point TurnRight() const {
        return {y,-x};
    }

    friend Point operator +(Point const &a,Point const &b) {
        return {a.x+b.x,a.y+b.y};
    }

    friend Point operator -(Point const &a,Point const &b) {
        return {a.x-b.x,a.y-b.y};
    }

    friend Point operator *(Point const &p,double const &k) {
        return {p.x*k,p.y*k};
    }

    friend double Inner(Point const &a,Point const &b) {
        return a.x*b.x+a.y*b.y;
    }

    friend double Outer(Point const &a,Point const &b) {
        return a.x*b.y-a.y*b.x;
    }

    friend double Dist(Point const &a,Point const &b) {
        return sqrt(Inner(a-b,a-b));
    }

    friend bool operator <(Point const &a,Point const &b) {
        return a.x<b.x || (a.x==b.x && a.y<b.y);
    }

    friend bool operator ==(Point const &a,Point const &b) {
        return a.x==b.x && a.y==b.y;
    }
}p[XN];

struct Circle {
    Point o;
    double r;

    bool Include(Circle const &a) {
        return sgn(a.r+Dist(o,a.o)-r)<=0;
    }
}o[XN];

struct Line {
    Point p,v;

    friend bool operator <(Line const &a,Line const &b) {
        return a.p<b.p || (a.p==b.p && a.v<b.v);
    }
};

double Dist(Point const &a,Line const &l) {
    return fabs(Outer(a-l.p,l.v))/l.v.Length();
}

bool OnLeft(Point const &p,Line const &ln) {
    return sgn(Outer(ln.v,p-ln.p))>0;
}

bool Paral(Line const &ln1,Line const &ln2) {
    return sgn(Outer(ln1.v,ln2.v))==0;
}

Point Cross(Line const &ln1,Line const &ln2) {
    if(Paral(ln1,ln2)) {
        return ln1.p+ln1.v*inf;
    } else {
        double t=Outer(ln2.v,ln1.p-ln2.p)/Outer(ln1.v,ln2.v);
        return ln1.p+ln1.v*t;
    }
}

Point CutPoint(Point const &p,Circle const &a) {
    if(sgn(Dist(p,a.o)-a.r)==0)
        return p;
    else {
        double x=Dist(p,a.o),cosa=a.r/x,sina=sqrt(1-cosa*cosa);
        Point v=(p-a.o).Unit(),
              t={v.x*cosa-v.y*sina,v.y*cosa+v.x*sina};
        return a.o+t*a.r;
    }
}

Point Mirror(Point const &p,Line const &l) {
    Point foot=l.p+l.v.Unit()*(Inner(p-l.p,l.v)/l.v.Length());
    return foot+(foot-p);
}

Line Cut(Circle const &a,Circle const &b) {
    /*a--b   b|
      ----   a|
      */
    if(sgn(a.r-b.r)==0) {
        return {a.o+(b.o-a.o).Unit().TurnRight()*a.r,b.o-a.o};
    } else {
        double d=Dist(a.o,b.o),
               x=a.r*d/(b.r-a.r);
        Point c=a.o+(a.o-b.o).Unit()*x,
              p=CutPoint(c,a);
        if(a.r>b.r) {
            p=Mirror(p,{a.o,b.o-a.o});
            return {p,c-p};
        } else
            return {c,p-c};
    }
}

std::vector<Line> Intersect(std::vector<Line> &ln) {
    std::sort(ln.begin(),ln.end(),[](Line const &a,Line const &b)->bool {
                auto Quad=[](Point const &a)->int {
                    return sgn(a.x)>0 && sgn(a.y)>=0?1:
                            (sgn(a.x)<=0 && sgn(a.y)>0?2:
                            (sgn(a.x)<0 && sgn(a.y)<=0?3:4));
                };
                int qa=Quad(a.v),qb=Quad(b.v);
                return qa==qb?sgn(Outer(b.v,a.v))<0:qa<qb;
            });
    static Point Qp[XN];static Line Qln[XN];
    int n=ln.size();
    int head,tail;Qln[head=tail=1]=ln[0];
    for(int i=1;i<n;++i) {
        while(tail-head>=1 && !OnLeft(Qp[tail-1],ln[i]))
            tail--;
        while(tail-head>=1 && !OnLeft(Qp[head],ln[i]))
            head++;
        Qln[++tail]=ln[i];
        if(Paral(Qln[tail-1],Qln[tail])){
            int d1=OnLeft(Qln[tail].p,Qln[tail-1]),d2=OnLeft(Qln[tail-1].p,Qln[tail]);
            if(!d1 || !d2) {
                tail--;
                if(d1)
                    Qln[tail]=ln[i];
            }
        }
        if(tail-head>=1)
            Qp[tail-1]=Cross(Qln[tail-1],Qln[tail]);
    }
    while(tail-head>=1 && !OnLeft(Qp[tail-1],Qln[head]))
        tail--;
    if(tail-head>=1)
        return std::vector<Line>(Qln+head,Qln+tail+1);
    else
        return {};
}

double ArcLen(double const &len,double const &r) {
    return r*asin(len/2/r)*2;
}

int main() {
    freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    srand(0x1f1f1f1f);
    int n;std::cin>>n;
    for(int i=1;i<=n;++i) {
        std::cin>>o[i].o.x>>o[i].o.y>>o[i].r;
        o[i].r+=10;
    }
    static bool ban[XN];
    for(int i=1;i<=n;++i)
        if(!ban[i]) {
            for(int j=1;j<=n;++j)
                if(i!=j && o[i].Include(o[j]))
                    ban[j]=1;
        }
    int cc=0;
    for(int i=1;i<=n;++i)
        if(!ban[i])
            o[++cc]=o[i];
    n=cc;
    double Ans=0;
    if(n==1)
        Ans=2*pi*o[1].r;
    else {
        std::map<Line,std::pair<int,int>> id;
        std::vector<Line> v;
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j) 
                if(i!=j) {
                    Line cut=Cut(o[i],o[j]);
                    /*
                    for(auto x : {o[i],o[j]})
                        std::cerr<<Dist(x.o,cut)<<' '<<x.r<<'\n';
                    */
                    bool tak=1;
                    for(int k=1;k<=n;++k)
                        tak&=OnLeft(o[k].o,cut) && sgn(Dist(o[k].o,cut)-o[k].r)>=0;
                    if(tak)
                        v.push_back(cut);
                }
        v=Intersect(v);
        int s=v.size();
        std::vector<std::array<Point,2>> cp(s);
        std::vector<int> ids(s);
        for(int i=0;i<s;++i) {
            double mx=-inf,mn=inf;
            for(int j=1;j<=n;++j) {
                Point pts[2];
                pts[1]=Mirror(pts[0]=CutPoint(v[i].p,o[j]),{v[i].p,o[j].o-v[i].p});
                for(int d=0;d<2;++d)
                    if(sgn(Outer(pts[d]-v[i].p,v[i].v))==0) {
                        double t=Inner(pts[d]-v[i].p,v[i].v)/v[i].v.Length2();
                        if(Enlarge(mx,t)) {
                            cp[(i+1)%s][0]=pts[d];
                            ids[(i+1)%s]=j;
                        }
                        if(Reduce(mn,t)) {
                            cp[i][1]=pts[d];
                        }
                        break;
                    }
            }
        }
        for(int i=0;i<s;++i)
            Ans+=Dist(cp[i][1],cp[(i+1)%s][0])+ArcLen(Dist(cp[i][0],cp[i][1]),o[ids[i]].r);
    }
    std::cout<<std::fixed<<std::setprecision(10)<<Ans<<'\n';
    return 0;
}

[ICPC 2017 ECNA E]Is-A? Has-A? Who Knowz-A?

Link

Solution

一道大水题,提醒自己用最暴力的方法做最对的事。

Code

const int XN=1000;

std::vector<int> is[XN],has[XN];

int main() {
//  freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
    std::map<std::string,int> id;
    int n,m;std::cin>>n>>m;
    int cnt=0;
    for(int i=1;i<=n;++i) {
        std::string c1,op,c2;
        std::cin>>c1>>op>>c2;
        for(auto & s: { c1,c2 })
            if(!id.count(s))
                id[s]=++cnt;
        int x=id[c1],y=id[c2];
        (op[0]=='i'?is[x]:has[x]).push_back(y);
    }

    for(int ks=1;ks<=m;++ks) {
        std::cout<<"Query "<<ks<<": ";
        std::string c1,op,c2;
        std::cin>>c1>>op>>c2;
        int x=id[c1],y=id[c2];
        bool tak=0;
        if(op[0]=='i') {
            std::queue<int> Q;
            std::set<int> S;
            Q.push(x);
            S.insert(x);
            while(!Q.empty()) {
                int pos=Q.front();Q.pop();
                for(auto u : is[pos]) {
                    if(u==y) {
                        tak=1;
                        goto out;
                    }
                    if(!S.count(u)) {
                        S.insert(u);
                        Q.push(u);
                    }
                }
            }
            tak=S.count(y);
        } else {
            std::queue<std::pair<int,bool>> Q;
            std::set<std::pair<int,bool>> S;
            Q.push({x,0});
            S.insert({x,0});
            while(!Q.empty()) {
                auto pos=Q.front();Q.pop();
                for(auto u : has[pos.first]) {
                    if(!S.count(std::pair<int,bool>(u,1))) {
                        Q.push({u,1});
                        S.insert({u,1});
                    }
                }
                for(auto u : is[pos.first])
                    if(!S.count(std::pair<int,bool>(u,pos.second))) {
                        Q.push({u,pos.second});
                        S.insert({u,pos.second});
                    }
            }
            tak=S.count({y,1});
        }
out:    std::cout<<(tak?"true":"false")<<'\n';
    }
    return 0;
}

[ICPC 2018 Asia Yokohama Onsite J]Colorful Tree

Link

Solution

年轻的时候见这种题比较多。。。
需要维护每种颜色的点的集合,和每种颜色点的LCA。
点的集合按照DFS序来存储,怎么维护想想就明白了。

Code

const int XN=1e5+11,XL=20;

#define log2 _log2

int log2[XN];
std::vector<int> G[XN];
int dfn[XN],dfs[XN],dfc,fa[XN],dep[XN];
int par[XN][XL];

void DFS(int pos) {
    par[pos][0]=fa[pos];
    for(int b=1;b<=log2[dep[pos]];++b)
        par[pos][b]=par[par[pos][b-1]][b-1];

    dfs[dfn[pos]=++dfc]=pos;

    for(auto u : G[pos]) if(u!=fa[pos]) {
        fa[u]=pos;
        dep[u]=dep[pos]+1;
        DFS(u);
    }
}

int LCA(int u,int v) {
    if(u==-1 || v==-1)
        return u==-1?v:u;
    else {
        if(dep[u]<dep[v])
            std::swap(u,v);
        for(int len=dep[u]-dep[v],b=log2[len];b>=0;--b)
            if(len>>b&1)
                u=par[u][b];
        if(u!=v) {
            for(int b=log2[dep[u]];b>=0;--b)
                if(par[u][b]!=par[v][b]) {
                    u=par[u][b];
                    v=par[v][b];
                }
            u=par[u][0];
        }
        assert(u);
        return u;
    }
}

int Dist(int u,int v,int lca=0) {
    return dep[u]+dep[v]-2*dep[lca?lca:LCA(u,v)];
}

int Ans[XN],subLCA[XN];
std::set<int> S[XN];

int Up(int pos,int c) {
    int up=0;
    auto iter=S[c].lower_bound(dfn[pos]);
    if(iter!=S[c].begin()) {
        auto pred=(--iter)++;
        int lca=LCA(dfs[*pred],pos);
        if(dep[up]<dep[lca])
            up=lca;
    }
    auto succ=++iter;
    if(succ!=S[c].end()) {
        int lca=LCA(dfs[*succ],pos);
        if(dep[up]<dep[lca])
            up=lca;
    }
    return up;
}

void Add(int pos,int c) {
    S[c].insert(dfn[pos]);
    if(subLCA[c]==-1)
        subLCA[c]=pos;
    else {
        int up=Up(pos,c);
        if(dep[up]<dep[subLCA[c]]) {
            Ans[c]+=Dist(subLCA[c],pos,up);
            subLCA[c]=up;
        } else
            Ans[c]+=dep[pos]-dep[up];
    }
}

void Delete(int pos,int c) {
    if(S[c].size()==1) {
        subLCA[c]=-1;
        S[c].erase(dfn[pos]);
    } else {
        int up=Up(pos,c);       
        S[c].erase(dfn[pos]);
        if(up==subLCA[c]) {
            int lca=S[c].size()==1?dfs[*S[c].begin()]:LCA(dfs[*S[c].begin()],dfs[*S[c].rbegin()]);
            Ans[c]-=Dist(lca,pos);
            subLCA[c]=lca;
        } else {
            Ans[c]-=dep[pos]-dep[up];
        }
    }
}

int main() {
    freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n;std::cin>>n;
    log2[0]=-1;
    for(int i=1;i<=n-1;++i) {
        int x,y;std::cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
        //std::cerr<<i<<':';
        log2[i]=log2[i>>1]+1;
    }
    dep[1]=1;
    DFS(1);

    memset(subLCA,-1,sizeof(subLCA));

    static int c[XN];
    for(int i=1;i<=n;++i) {
        std::cin>>c[i];
        Add(i,c[i]);
    }
    int m;std::cin>>m;
    for(int q=1;q<=m;++q) {
        char op;int x,y;
        std::cin>>op>>x;
        if(op=='Q') {
            if(S[x].empty())
                std::cout<<-1<<'\n';
            else
                std::cout<<Ans[x]<<'\n';
        } else {
            std::cin>>y;
            Delete(x,c[x]);
            Add(x,c[x]=y);
        }
    }
    return 0;
}

[ZOJ Monthly, January 2019]Little Sub and his Geometry Problem

Link

Solution

Q很小,每次询问可以O(n)。注意到,对于满足要求的(u,v),随着u的增大,v是单调递减的,就很好做了。
关键就是注意到这个单调性

Code

#include <bits/stdc++.h>

const int XN=1e5+11;

void Work() {
    static std::pair<int,int> p[XN];
    int w,n,q;
    std::cin>>w>>n;
    for(int i=1;i<=n;++i)
        std::cin>>p[i].first>>p[i].second;
    std::sort(p+1,p+1+n);
    std::cin>>q;
    while(q--) {
        long long c;std::cin>>c;
        int y=w,Ans=0;
        static int yc[XN];
        static long long ys[XN];
        for(int i=1;i<=w;++i)
            yc[i]=ys[i]=0;
        int cnt=0;long long sum=0;
        for(int x=1,i=1;x<=w;++x) {
            while(p[i].first==x) {
                if(p[i].second<=y) {
                    cnt++;sum+=p[i].first+p[i].second;
                    yc[p[i].second]++;ys[p[i].second]+=p[i].first+p[i].second;
                }
                i++;
            }
            while((long long)cnt*(x+y)-sum>c) {
                cnt-=yc[y];
                sum-=ys[y];
                y--;
            }
            if((long long)cnt*(x+y)-sum==c)
                Ans++;
        }
        std::cout<<Ans<<(q?' ':'\n');
    }
}

int main() {
//  freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int T;std::cin>>T;
    while(T--)
        Work();
    return 0;
}