第1届ICPC青少年程序设计竞赛 部分题目题解

比赛链接

C.Chocolate Counting

给定质数 \(p\)（\(p\ge 3\)）与整数 \(k\)，求在 \(1\sim kp\) 中选择 \(p\) 个互不相同的数，满足和为 \(p\) 的倍数的方案数。\(p,k\le 10^7\)。

Solution

对于某些模质数 \(p\) 的余数相关的计数题，可以考虑将选择方案分组，满足每组中 \(p\) 个方案的结果模 \(p\) 余数方案互不相同。

将 \(1\sim kp\) 放在一个 \(p\times k\) 的矩阵上，第 \(i\) 行依次放置 \(i,i+p,i+2p,\dots i+(k-1)p\)。

考虑在矩阵上随机选择 \(p\) 个数，如果这 \(p\) 个数恰好是同一列的 \(p\) 个数，那么它们直接合法。否则，考虑找到从左到右任意一个被选了数的列，将其上被选择的数循环移位，得到 \(p\) 个选择方案，那么显然有这 \(p\) 个选择方案 \(\mod p\) 的余数恰好为 \(0\sim p-1\)。

由此，可以将剩下的所有 \(\dbinom{pk}{p}-k\) 中方案，\(p\) 个为一组分成若干组，每组中恰好有一个方案合法，因此这部分对答案的贡献就是 \(\dfrac{1}{p}(\dbinom{pk}{p}-k)\)。

#include
using namespace std;
typedef long long ll;
const int mod=998244353,N=1e7+10;
int T,p,k,fac[N],inv[N];
inline int add(int x,int y){return (x+y>=mod)?x+y-mod:x+y;}
inline int dec(int x,int y){return (x-y<0)?x-y+mod:x-y;}
inline void init(int n){
    inv[0]=inv[1]=1;
    for(int i=2;i<=n;++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
}
int main(){
    scanf("%d",&T);
    init(10000000);
    while(T--){
        scanf("%d%d",&p,&k);
        ll now=1ll*p*k;int ans=1;
        for(int i=1;i<=p;++i) ans=1ll*ans*(now%mod)%mod*inv[i]%mod,now--;
        printf("%d\n",add(1ll*dec(ans,k)*inv[p]%mod,k));
    }
    return 0;
}

G.Dynamic Graph

给定一个 \(n\) 个点的无向图以及一个常数 \(F\)，一开始没有边。

你需要执行 \(m\) 次操作。

操作有 \(3\) 种：

1 u v w: 在 \(u\) 和 \(v\) 之间加了一条权值为 \(w\) 的边。

2 id: 删除第 \(id\) 次操作添加的边。

3 u v w: 询问是否存在一条权值和模 \(F\) 余 \(w\) 的从 \(u\) 到 \(v\) 的路径（可以不是简单路径）。

\(n,m\le 10^5,F\le 10^9\)。

Solution

经典套路：对于询问某个两个点之间是否存在路径权值 \(\mod F=w\) 的问题。可以先取出两点之间任意一条路径，设长度为 \(x\)，求出两点所在连通块所有环长的 \(\gcd\) 设为\(G\)，那么能取到 \(w\) 当且仅当 \(w\equiv kG+x\pmod F(k\in Z)\)。

对这个结论的证明也很简单，就是先取出任意一条路径，然后可以通过从某个点出发向环上任意一点来回走 \(F\) 遍，在中途绕环若干圈将环长叠加进路径答案中。

那么对于原问题，我们首先通过线段树分治去掉删除操作。对于添加边 \((u,v,w)\) 的操作，如果 \(u,v\) 在同一连通块中，设 \(d_u,d_v\) 分别为 \(u,v\) 到根的路径长，则更新该连通块最大公约数 \(G=\gcd(G,2w,w+d_u+d_v)\)。如果 \(u,v\) 不在同一连通块中，合并这两个连通块，新块的最大公约数 \(G=\gcd(G_1,G_2,2w)\)。

于是使用按秩合并并查集维护，复杂度为 \(\mathcal O(n\log ^2 n)\)（假设 \(n,m\) 同阶）。

#include
using namespace std;
const int N=1e5+10;
struct edge{
    int u,v,w;
}e[N];
int n,m,tot,id[N],mod,st[N],ed[N];
inline int add(int x,int y){return (x+y>=mod)?x+y-mod:x+y;}
inline int dec(int x,int y){return (x-y<0)?x-y+mod:x-y;}
vector que[N];

namespace DSU{
    int fa[N],siz[N],up[N],g[N],top;
    int stk[N][6];
    inline int find(int x){return fa[x]==x?fa[x]:find(fa[x]);}
    inline int gval(int x){return fa[x]==x?0:add(gval(fa[x]),up[x]);}
    inline void merge(int u,int v,int w){
        int x=add(gval(u),gval(v));
        u=find(u);v=find(v);
        if(siz[u]x){
            int u=stk[top][0],v=stk[top][1];
            g[u]=stk[top][2];fa[v]=stk[top][3];
            siz[u]=stk[top][4];up[v]=stk[top][5];
            --top;
        }
    }
    inline void qry(int x,int u,int v,int w){
        int now=dec(w,add(gval(u),gval(v)));
        if(now%g[x]==0) puts("1");
        else puts("0");
    }
}
using namespace DSU;
namespace SGT{
    #define lc (p<<1)
    #define rc (p<<1|1)
    #define mid ((l+r)>>1)
    vectortr[N<<2];
    inline void update(int p,int ql,int qr,int x,int l=1,int r=m){
        if(ql<=l&&r<=qr){tr[p].push_back(x);return ;}
        if(ql<=mid) update(lc,ql,qr,x,l,mid);
        if(qr>mid) update(rc,ql,qr,x,mid+1,r); 
    }
    inline void solve(int p=1,int l=1,int r=m){
        int now=top;
        for(int x:tr[p]) merge(e[x].u,e[x].v,e[x].w);
        if(l==r){
            for(auto e:que[l]){
                if(find(e.u)!=find(e.v)) puts("0");
                else qry(find(e.u),e.u,e.v,e.w);
            }
        }
        if(l!=r) solve(lc,l,mid),solve(rc,mid+1,r);
        rollback(now);
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&mod);
    for(int i=1;i<=n;++i) fa[i]=i,siz[i]=1,g[i]=mod;
    for(int i=1;i<=m;++i){
        int op;scanf("%d",&op);
        if(op==1){
            ++tot;id[i]=tot;
            scanf("%d%d%d",&e[tot].u,&e[tot].v,&e[tot].w);
            st[tot]=i;ed[tot]=-1;
        }
        else if(op==2){
            int x;
            scanf("%d",&x);
            ed[id[x]]=i;
        }
        else{
            int u,v,w;scanf("%d%d%d",&u,&v,&w);
            que[i].push_back((edge){u,v,w});
        }
    }
    for(int i=1;i<=tot;++i){
        if(~ed[i]) SGT::update(1,st[i],ed[i],i);
        else SGT::update(1,st[i],m,i);
    }
    SGT::solve();
    return 0;
}