Solution0815

一:求和(modsum)

题目描述

求$$\sum_{i=1}^{n}\sum_{j=1且i\ne j}^{m}(n\;mod\;i)(m\;mod\;j)$$

数据范围

$n,m\le 10Y9$

思路

考虑没有$i \ne j$的限制,

那么答案为

$$(\sum_{i=1}^{n}n\;mod\;i)\times(\sum_{j=1}^{m}m\;mod\;j)$$

显然整除分块。

题解1027

设$m<n$,还要减去

$$\sum_{i=1}^{m}(n\; mod \; i)(m \; mod\;i)$$

把取模化简:

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

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

$$m^2n-mn\sum_{i=1}^{m}i\lfloor\frac{m}{i}\rfloor-\sum_{i=1}^{m}i\lfloor\frac{n}{i}\rfloor+\sum_{i-1}^{m}i^2\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor$$

前两个$\sum$显然可以分块,而$$\sum_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6}$$

,所以第三个也可以,只是同时后两个被除数,稍微麻烦,具体见代码calc2()。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define REP(i,a,b) for(int i = (a);i <= (b);i++)
#define PER(i,a,b) for(int i = (a);i >= (b);i--)
#define SF scanf
#define PF printf
#define MOD 19940417ll
//#define int long long
using namespace std;
typedef long long ll;
const ll inv6 = 3323403ll;
ll n,m;
ll ans;
ll pre(ll x){
    ll res = 0ll;
    for(ll l = 1,r;l <= x;l = r + 1){
        r = x / (x / l);
        res = (res + (x % r + x % l) * (r - l + 1) / 2ll) % MOD;
    }
    return res;
}
ll calc1(ll x,ll num){
    ll res = 0ll;
    for(ll l = 1,r;l <= num;l = r + 1){
        r = x / (x / l);ll R = min(num,r);
        (res += (R + l) * (R - l + 1) / 2ll * (x / l)) %= MOD;
    }
    return res;
}
ll sum(ll x){
    return (ll)(x) * (ll)(x + 1) % MOD * (ll)(x * 2 + 1) % MOD * inv6 % MOD;
}
ll calc2(){
    ll r1, r2, x = 1, y;
    ll res = 0;
    while(x <= m){
        r1 = n / (n / x);
        r2 = m / (m / x);
        y = min(m,min(r1,r2));
        res = res + (n / y) * (m / y) % MOD * ((sum(y) - sum(x - 1) + MOD) % MOD) % MOD;
        x = y + 1;
    }
    return res;
}
signed main()
{
    cin>>n>>m;
    if(n < m)swap(n,m); //n >= m
    ans = pre(n) * pre(m) % MOD;
    ll dec = ((m * m % MOD * n % MOD - m * calc1(n,m) % MOD - n * calc1(m,m) % MOD + calc2()) % MOD + MOD);
    ans = ((ans - dec) % MOD + MOD) % MOD;
    cout<<ans<<endl;
    return 0;
}

二:排队queue

题目描述

CZ 一共雇佣了 N 个保镖(编号为 1 到 N),他在其余
N-1 个保镖里,都会有一个“上司”,但一号保镖例外,没有上司。
CZ 会对这 N 个保镖进行定期视察。每次视察的时候,首先会让所有保镖排队。
现在 CZ 要求排出来的队伍满足:

  • 互为上司-下属的两个保镖,上司在前,下属在后
  • 对于一个保镖的所有下属,武功实力较强的在前,较弱的在后。

CZ 想知道,总的排队方法数除以 10007 的余数是多少。

思路

每个人只有一个上司,所以关系时一棵树。

考虑dp,那么当前人的所有下属已经形成了排列,考虑如何合并到当前人的状态。

考虑倒序枚举下属(由弱到强),那么对于之前人已经形成的排列,当前人必须排在序列的最前面,他之后的人则可以随便插空,因此

假设F(u)为当前树u的dp值,已经计算的子树size和为n,当前子树v的size为m:

$$F(u)=F(u)\times \binom{n+m-1}{m-1}*F(v)$$

代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define REP(i,a,b) for(int i = (a);i <= (b);i++)
#define PER(i,a,b) for(int i = (a);i >= (b);i--)
#define SF scanf
#define PF printf
#define N 1001
#define MOD 10007
using namespace std;
int T,n;
int len[N],a[N][N];
int f[N];
int c[N + 10][N + 10];
int dfs(int u){
    if(f[u])return f[u];
    int size = 1;
    if(!len[u]){f[u] = 1;return 1;}
    f[u] = 1;
    PER(i,len[u],1){
        int v = a[u][i];
        int t = dfs(v);
        size += t;
        f[u] *= (c[size - 2][t - 1] * f[v]) % MOD;
        f[u] %= MOD;
    }
    return size;
}
int main()
{
    REP(i,0,N)c[i][0] = 1;
    REP(i,1,N)REP(j,1,i)
        c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
    cin>>T;
    while(T--){
        memset(f,0,sizeof f);
        SF("%d",&n);
        REP(i,1,n){
            SF("%d",&len[i]);
            REP(j,1,len[i])
                SF("%d",&a[i][j]);
        }
        dfs(1);
        PF("%d\n",f[1]);
    }
    return 0;
}

非常优美。


三:城市(city)

题目描述

某国有 N 座城市(依次编号为 1 到 N),又有 M 条道路连接了其中的城市,每一条道路都连接
了不同的 2 个城市,任何两座不同的城市之间可能不止一条道路。该国女王赋予了每一座城市不
同的能量,其中第 i 座城市被赋予的能量为 Wi。
如果城市 u 和 v 之间有一条道路,那么只要此刻女王的能量不小于|Wu-Wv|,这条道路就是安
全的。如果城市 u 和 v 之间存在两条没有重复道路的安全路径(其中每一段道路都是安全的),
则认为这两座城市之间有着良好的贸易关系。
最近,该国女王因为情感问题,她的能量产生巨大的波动。为了维持该国的经济贸易,她希望
你能帮忙对 Q 对城市进行调查。对于第 j 对城市 uj 和 vj,她希望知道在保证这两座城市之间有
着良好贸易关系的前提之下,自己最少需要保持多少的能量。

数据范围

$3\le N<=100000, 3\le M\le 500000, 1\le Q\le 100000,
0\le Wile 200000$

思路

暴力:二分+tarjan

正解:

首先考虑只需要一条路径的情况,那么显然是最小生成树(Kruskal)+倍增lca,

考虑加入非树边产生的影响。对于非树边(u,v),边权x,显然把树上u→v的路径全部更新成x就行了。

又因为Kruskal将边排序,u→v被更新后一定不会再被更新了,就将他们缩起来,于是用并查集维护每个点缩起来后上方的父亲,更新时暴力向上跳。

代码

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cctype>
#include <cmath>

using namespace std;

int read()
{
    int x=0,f=1;
    char ch=getchar();
    while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
    while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    return x*f;
}

int buf[30];

void write(int x)
{
    if (x<0) x=-x,putchar('-');
    for (;x;x/=10) buf[++buf[0]]=x%10;
    if (!buf[0]) buf[++buf[0]]=0;
    for (;buf[0];) putchar('0'+buf[buf[0]--]);
}

const int N=100050;
const int M=500050;
const int E=N<<1;
const int LGN=17;

struct edge
{
    int x,y,l;
}e[M];

bool operator<(edge a,edge b){return a.l<b.l;}

int fa[N],deep[N],last[N],w[N];
int f[N][LGN],anc[N][LGN];
int tov[E],nxt[E],len[E];
int n,m,q,tot,lgn,ans;
bool chosen[M];

int getfather(int son){return fa[son]==son?son:fa[son]=getfather(fa[son]);}

void insert(int x,int y,int z){tov[++tot]=y,len[tot]=z,nxt[tot]=last[x],last[x]=tot;}

void dfs(int x)
{
    for (int i=last[x],y;i;i=nxt[i])
        if ((y=tov[i])!=anc[x][0])
            anc[y][0]=x,deep[y]=deep[x]+1,f[y][0]=len[i],dfs(y);
}

void pre()
{
    lgn=trunc(log(n)/log(2));
    for (int j=1;j<=lgn;j++)
        for (int i=1;i<=n;i++)
            anc[i][j]=anc[anc[i][j-1]][j-1],f[i][j]=max(f[i][j-1],f[anc[i][j-1]][j-1]);
}

int adjust(int x,int d)
{
    for (int i=lgn;i>=0;i--)
        if (deep[anc[x][i]]>=d) ans=max(ans,f[x][i]),x=anc[x][i];
    return x;
}

void getans(int x,int y)
{
    ans=0;
    if (deep[x]>deep[y]) swap(x,y);
    y=adjust(y,deep[x]);
    if (x==y) return;
    for (int i=lgn;i>=0;i--)
        if (anc[x][i]!=anc[y][i]) ans=max(ans,max(f[x][i],f[y][i])),x=anc[x][i],y=anc[y][i];
    ans=max(ans,max(f[x][0],f[y][0])),x=anc[x][0],y=anc[y][0];
}

int main()
{
    freopen("city.in","r",stdin),freopen("city.out","w",stdout);
    n=read(),m=read(),q=read();
    for (int i=1;i<=n;i++) w[i]=read(),fa[i]=i;
    for (int i=1;i<=m;i++) e[i].x=read(),e[i].y=read(),e[i].l=abs(w[e[i].x]-w[e[i].y]);
    sort(e+1,e+1+m);
    for (int i=1,x,y,fx,fy;i<=m;i++)
    {
        fx=getfather(x=e[i].x),fy=getfather(y=e[i].y); 
        if (fx!=fy)
        {
            chosen[i]=1;
            fa[fy]=fx;
            insert(x,y,e[i].l),insert(y,x,e[i].l);
        }
    }
    anc[1][0]=0,deep[1]=1,dfs(1);
    for (int i=1;i<=n;i++) fa[i]=i;
    for (int i=1,x,y;i<=m;i++)
        if (!chosen[i])
            for (x=getfather(e[i].x),y=getfather(e[i].y);x!=y;x=getfather(x))
            {
                if (deep[x]<deep[y]) swap(x,y);
                f[x][0]=max(e[i].l,f[x][0]);
                fa[x]=anc[x][0];
            }
    pre();
    for (int x,y;q--;)
    {
        x=read(),y=read();
        if (getfather(x)!=getfather(y)||x==y) printf("infinitely\n");
        else getans(x,y),write(ans),putchar('\n');
    }
    //fclose(stdin),fclose(stdout);
    return 0;
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注