HGOI20190815 题解

Problem A modsum

求$\sum\limits_{i=1}^{n} \sum\limits_{j=1 , i \neq j}^{m} (n \ mod \ i)(m \ mod \ j)$

在模$ 19940417 $的意义下计算答案。

对于$100\%$的数据，满足$1 \leq n,m \leq 10^9$

Solution :

由于$n,m$的答案和$m,n$的答案都是一样的，我们不妨令$n\leq m$

一眼想到了整除分块，我们显然可以通过$O(\sqrt{n})$的复杂度求出

$G(n,k) = \sum\limits_{i=1}^{n} (k \ mod \ i)$的值。

我们考虑化简原来的式子，原式$ = \sum\limits_{i=1}^{n} ((\sum\limits_{j=1}^{m} (n\ mod \ i)(m \ mod \ j))- (n \ mod \ i)(m \ mod \ i))$

$ = \sum\limits_{i=1}^n\sum\limits_{j=1}^{m}(n \ mod \ i)(m \ mod \ j) - \sum\limits_{i=1}^{n} (n \ mod \ i)(m \ mod \ i)$

$ = \sum_{i=1}^n\sum_{j=1}^{m}(n \ mod \ i)(m \ mod \ j) -\sum_{i=1}^{n}(n-i\times \left \lfloor \frac{n}{i} \right \rfloor)(m-i\times \left \lfloor \frac{m}{i} \right \rfloor)$

$== \sum_{i=1} ^n (n \ mod \ i)\sum_{i=1}^{m} (m \ mod \ i)- n^2 m + m\sum_{i=1}^{n} i \times \left \lfloor \frac{n}{i} \right \rfloor + n\sum_{i=1}^{n} i \times \left \lfloor \frac{m}{i} \right \rfloor - \sum_{i=1}^{n} \left \lfloor \frac{n}{i} \right \rfloor \left \lfloor \frac{m}{i} \right \rfloor i^2$

对于$ \sum_{i=1}^{n} \left \lfloor \frac{n}{i} \right \rfloor \left \lfloor \frac{m}{i} \right \rfloor i^2$的求法可以整除分块，每一次跳最小值来实现。

由于最多是有$2\sqrt{n}$条线，所以复杂度是$O(\sqrt{n})$

注意到$19940417$ 不是质数，然而$\sum_{i=1}^{n} i^2 = \frac{n\times(n+1)\times(2n+1)}{6}$中的$6$和它是互质的，所以可以简单的for循环求逆元即可。

# include <bits/stdc++.h>

# define int long long

using namespace std;

const int mo=;

int inv6=;

int inv2=;

int mul(int x,int n)

{

    int ans=;

    while (n) {

        if (n&) ans=(ans+x)%mo;

        n>>=;

        x=(x+x)%mo;

    }

    return ans%mo;

}

int fun(int l,int r){

    l--;

    return (((mul(mul(r,r+),*r+)*inv6)%mo-(mul(mul(l,l+),*l+)*inv6)%mo)%mo+mo)%mo;

}

int calc1(int n,int m)

{

    int ret=;

    for (int l=,r1,r2,r;l<=n;l=r+) {

        if (n/l!=) r1=min(n/(n/l),n); else r1=n;

        if (m/l!=) r2=min(m/(m/l),n); else r2=m;

        r=min(r1,r2);

        ret=(ret + mul(mul((n/l),(m/l)),fun(l,r)))%mo;

    }

    return ret%mo;

}

int calc(int n,int k) {

    int ret=;

    for (int l=,r;l<=n;l=r+) {

        if (k/l!=) r=min(k/(k/l),n);

        else r=n;

        ret=(ret + mul(mul(mul(k/l,(r-l+)),(l+r)),inv2))%mo;

    }

    return ret%mo;

}

int G(int n,int k) { return ((mul(n,k)-calc(n,k))%mo+mo)%mo;}

signed main()

{

    int n,m; scanf("%lld%lld",&n,&m);

    if (n>m) swap(n,m);

    int ans=mul(G(n,n),G(m,m))-mul(mul(n,n),m)+mul(m,calc(n,n))+mul(n,calc(n,m))-calc1(n,m);

    printf("%lld\n",(ans%mo+mo)%mo);

    return ;

}

A.cpp

Problem B queue

给出一棵多叉树，求关于所有节点的排列数，要求：

　 1. 每棵子树的根节点先于这棵子树的其他节点出现。

　 2. 和一个节点直接相连的节点必须依次出现但可不连续。

在$mod \ 10007$ 意义下询问排列数。
对于$100\%$的数据$1 \leq n\leq 10^3$

Solution :

可以将多叉树转化为二叉树，答案显然不变。

　一种显然的转化方法就是将每个点的儿子按照一条链连接下去，这样一定保证是二叉树。

设$f[u]$表示将$u$的子树排列的可行数目，显然从$f[l_{son}]$和$f[r_{son}]$转移过来。

显然，$f[u] = f[l_{son}] \times f[r_{son}] \times C_{size[l_{son}]+size[r_{son}]}^{size[l_{son}]}$

其中合并的贡献就是在$size[l_{son}]+size[r_{son}]$个位置上放$size[l_{son}]$个数字的方案数（顺序没有关系）。

复杂度是预处理组合数的复杂度是$O(n^2)$　　

# include <bits/stdc++.h>

# define int long long

using namespace std;

const int N=;

const int mo=;

vector<int>E[N];

int c[N][N],n,size[N],f[N];

int C(int n,int m){return c[n][m];}

void dfs(int u)

{

    if (E[u].size()==) {

        size[u]=; f[u]=;

        return;

    }

    if (E[u].size()==) {

        dfs(E[u][]); size[u]=size[E[u][]]+;

        f[u]=f[E[u][]];

    }

    if (E[u].size()==) {

        dfs(E[u][]); dfs(E[u][]);

        size[u]=size[E[u][]]+size[E[u][]]+;

        f[u]=f[E[u][]]*f[E[u][]]%mo*C(size[E[u][]]+size[E[u][]],size[E[u][]])%mo;

    }

}

signed main()

{

    c[][]=;

    for (int i=;i<=;i++) {

        c[i][]=c[i][i]=;

        for (int j=;j<i;j++)

         c[i][j]=(c[i-][j-]+c[i-][j])%mo;

    }

    int T; scanf("%lld",&T);

    while (T--) {

        scanf("%lld",&n);

        for (int i=;i<=n;i++) f[i]=;

        for (int i=;i<=n;i++) E[i].clear();

        for (int i=;i<=n;i++) {

            int k; scanf("%lld",&k);

            int nowf=i;

            for (int j=;j<=k;j++) {

                int x; scanf("%lld",&x);

                E[nowf].push_back(x);

                nowf=x;

            }

        }

        dfs();

        printf("%lld\n",f[]);

    }

    return ;

}

B.cpp

Problem C city

每个点的点权是$w[i]$，经过一条边的代价是$|w[u] - w[v]|$.

定义一条路径$val_S$的代价是路径经过边的最大代价，即$val_S = max\{w[Edge] (Edge \in S)\}$

设需要的能量为$D$,设两点存在“正常的关系”为：至少有两条不重叠的路径$S,T$使得$D \leq val_S , D \leq val_T$

询问$u,v$是否是可能是正常的关系，如果是，输出所需最少能量$D$，否则输出"infinitely"

对于$100\%$的数据$n,m,q \leq 5\times 10^5 $

Solution :

　　建出最小生成树，这样树边都不是可行边，从小到大拿非树边取更新答案。

　　由于非树边$(u,v)$添加上后会形成环，就存在边双了，这个环上的所有点的答案就是这条边的权值。

　　我们只需要将这些点的答案用这条边的权值更新掉即可。

　　由于边权排序了，所以后面的边来更新一定不是最优的，所以我们只需要用一个并查集将树上路径折叠掉即可。

　　询问的时候直接求一遍倍增lca即可。

　　复杂度是$O(n \ log_2 \ n)$

# include<bits/stdc++.h>

using namespace std;

const int N=1e5+,M=5e5+;

struct rec{ int pre,to,w;}a[N<<];

struct A{ int u,v,w;}Edge[M];

bool cmp(A a,A b){return a.w<b.w;}

int tot,n,m,q,val[N],g[N][],d[N][],f[N],head[N],dep[N];

bool inTree[M];

void adde(int u,int v)

{

    a[++tot].pre=head[u];

    a[tot].to=v;

    head[u]=tot;

}

int father(int x)

{

    if (f[x]==x) return x;

    return f[x]=father(f[x]);

}

void kruskal()

{

    for (int i=;i<=n;i++) f[i]=i;

    sort(Edge+,Edge++m,cmp);

    for (int i=;i<=m;i++) {

        int fx=father(Edge[i].u),fy=father(Edge[i].v);

        if (fx == fy) continue;

        f[fy] = fx;

        adde(Edge[i].u,Edge[i].v);

        adde(Edge[i].v,Edge[i].u);

        inTree[i]=;

    }

}

void dfs(int u,int fa)

{

    g[u][]=fa; dep[u]=dep[fa]+;

    for (int i=head[u];i;i=a[i].pre) {

        int v=a[i].to; if (v==fa) continue;

        dfs(v,u);

    }

}

void init()

{

    for (int i=;i<=;i++)

     for (int j=;j<=n;j++)

      g[j][i]=g[g[j][i-]][i-],

      d[j][i]=max(d[j][i-],d[g[j][i-]][i-]);

}

int query(int u,int v){

    int ret=;

    if (dep[u]<dep[v]) swap(u,v);

    for (int i=;i>=;i--)

     if (dep[g[u][i]]>=dep[v]) ret=max(ret,d[u][i]),u=g[u][i];

    if (u==v) return ret;

    for (int i=;i>=;i--) if (g[u][i]!=g[v][i]) {

        ret=max(max(ret,d[u][i]),d[v][i]);

        u=g[u][i]; v=g[v][i];

    }

    return max(ret,max(d[u][],d[v][]));

}

int main()

{

//  freopen("city.in","r",stdin);

//  freopen("city.out","w",stdout);

    scanf("%d%d%d",&n,&m,&q);

    for (int i=;i<=n;i++) scanf("%d",&val[i]);

    for (int i=;i<=m;i++)

     scanf("%d%d",&Edge[i].u,&Edge[i].v),Edge[i].w=abs(val[Edge[i].v]-val[Edge[i].u]);

    kruskal();  dfs(,);

    for (int i=;i<=n;i++) f[i]=i;

    for (int i=;i<=m;i++) if (!inTree[i]) {

        int fx=father(Edge[i].u),fy=father(Edge[i].v);

        while (fx!=fy) {

            if (dep[fx]<dep[fy]) swap(fx,fy);

            d[fx][]=Edge[i].w; f[fx]=g[fx][]; fx=father(fx);

        }

    }

    init();

    while (q--) {

        int u,v; scanf("%d%d",&u,&v);

        if (father(u)!=father(v)) puts("infinitely");

        else printf("%d\n",query(u,v));

    }

    return ;

}

C.cpp

巴特西

HGOI20190815 题解

最新文章

热门文章