HDU 多校 2023 Round #5 题解

\(\text{By DaiRuiChen007}\)

A. Typhoon

Problem Link

题目大意

给一条 \(n\) 个点构成的折线，\(q\) 次询问某个点到折线的最短距离。

数据范围：\(n,q\le 10^4\)。

思路分析

暴力枚举每一条线段，判断点到直线的垂足是否在线段上即可。

时间复杂度 \(\mathcal O(nm)\)。

代码呈现

#include<bits/stdc++.h>
#define ll long long
#define double long double
using namespace std;
const int MAXN=1e4+5;
const double inf=1e18,eps=1e-6;
struct Point { ll x,y; } a[MAXN];
Point operator -(Point x,Point y){x.x-=y.x,x.y-=y.y;return x;}
ll operator *(Point x,Point y){return abs(x.x*y.y-x.y*y.x);} 
inline ll dis(Point A,Point B){
    return (A.x-B.x)*(A.x-B.x)+(B.y-A.y)*(B.y-A.y);
}
inline double dist(Point p,Point A,Point B) {
    ll a=dis(p,A),b=dis(p,B),c=dis(A,B);
    if(c&&a+c>=b&&b+c>=a) return (A-p)*(A-B)/sqrt(c);
    else return sqrt(min(a,b)); 
}
signed main() {
    int n,q;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;++i) scanf("%lld%lld",&a[i].x,&a[i].y);
    for(Point p;q--;) {
        scanf("%lld%lld",&p.x,&p.y);
        double ans=inf;
        for(int i=1;i<n;++i) ans=min(ans,dist(p,a[i],a[i+1]));
        printf("%.4Lf\n",ans);
    }
    return 0;
}

B. GCD Magic

Problem Link

题目大意

给定 \(n,p\)，求下式的值：

\[\sum_{i=1}^n\sum_{j=1}^n\gcd(2^i-1,2^j-1)^p \]
数据访问：\(n\le 10^9,p\le 10\)。

思路分析

首先根据辗转相除法可以证明 \(\gcd(2^i-1,2^j-1)=2^{\gcd(i,j)}-1\)，枚举 \(k=\gcd(i,j)\) 后莫比乌斯反演得到：

\[\begin{aligned} \text{Answer} &=\sum_{i=1}^n\sum_{j=1}^n2^{\gcd(i,j)}-1\\ &=\sum_{k=1}^n (2^k-1)^p\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=1]\\ &=\sum_{k=1}^n (2^k-1)^p\sum_{i=1}^{\lfloor n/k\rfloor}\sum_{j=1}^{\lfloor n/k\rfloor}\sum_{d\mid \gcd(i,j)}\mu(d)\\ &=\sum_{k=1}^n (2^k-1)^p\sum_{d=1}^{\lfloor n/k\rfloor}\mu(d)\left\lfloor\dfrac{n}{kd}\right\rfloor^2\\ &=\sum_{t=1}^n\left\lfloor\dfrac nt\right\rfloor^2\sum_{k\times d=t} \mu(d)(2^k-1)^p \end{aligned} \]

若定义 \(f(k)=(2^k-1)^p\)，则对 \(\left\lfloor\dfrac nt\right\rfloor\) 做整除分块后相当于块筛 \(f*\mu\) 的前缀和，记 \(f*\mu=g\)，注意到 \(g*1=f\)，因此根据杜教筛可以得到：

\[S(n)=\sum_{i=1}^nf(i)-\sum_{i=2}^nS\left(\left\lfloor\dfrac ni\right\rfloor\right) \]

其中 \(S(n)\) 表示 \(g(i)\) 的前缀和，做一遍杜教筛即可，\(f(i)\) 前缀和可以直接二项式展开成求 \(p+1\) 个等差数列的前缀和。

时间复杂度 \(\mathcal O((k\sqrt n+n^{2/3})\log n)\)，瓶颈在计算 \(f(i)\) 的前缀和以及 \(S(n)\) 在 \(1\sim n^{2/3}\) 范围内的点值。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5,MOD=998244353;
int n,m,k,B,mu[MAXN],C[15][15];
vector <int> primes,Mu;
bool isc[MAXN];
int idx1[MAXN],idx2[MAXN],val[MAXN];
int s0[MAXN],res[MAXN];
inline int ksm(int a,int b=MOD-2,int p=MOD) {
    int ret=1;
    while(b) ret=(b&1?1ll*ret*a%p:ret),a=1ll*a*a%p,b=b>>1;
    return ret;
}
inline int idx(int k) { return k<=B?idx1[k]:idx2[n/k]; }
inline int calc(int n) { 
    int ans=k&1?(MOD-n):n;
    for(int j=1,p=1;j<=k;++j) {
        p=(p<<1)%MOD;
        int tmp=1ll*(ksm(p,n)-1)*p%MOD*ksm(p-1)%MOD*C[k][j]%MOD;
        if((k-j)&1) ans=(ans+MOD-tmp)%MOD;
        else ans=(ans+tmp)%MOD;
    }
    return ans;
}
inline void solve() {
    scanf("%d%d",&n,&k),m=0,B=sqrt(n);
    for(int l=1,r;l<=n;l=r+1) {
        r=n/(n/l),val[++m]=n/l;
        if(val[m]<=B) idx1[val[m]]=m;
        else idx2[n/val[m]]=m;
    }
    memset(s0,0,sizeof(s0));
    for(int i=1,p=1;i<MAXN;++i) {
        p=(p<<1)%MOD;
        int f=ksm(p-1,k);
        for(int j:Mu) {
            if(i*j>=MAXN) break;
            if(mu[j]==1) s0[i*j]=(s0[i*j]+f)%MOD;
            else s0[i*j]=(s0[i*j]+MOD-f)%MOD;
        }
    }
    for(int i=1;i<MAXN;++i) s0[i]=(s0[i]+s0[i-1])%MOD;
    for(int i=m;i>=1;--i) {
        int t=val[i];
        if(t<MAXN) res[i]=s0[t];
        else {
            res[i]=calc(t);
            for(int l=2,r;l<=t;l=r+1) {
                r=t/(t/l);
                res[i]=(res[i]+MOD-1ll*(r-l+1)*res[idx(t/l)]%MOD)%MOD;
            }
        }
    }
    int ans=0;
    for(int l=1,r;l<=n;l=r+1) {
        r=n/(n/l);
        int sum=l==1?res[idx(r)]:(res[idx(r)]+MOD-res[idx(l-1)])%MOD;
        ans=(ans+1ll*(n/l)*(n/l)%MOD*sum%MOD)%MOD;
    }
    printf("%d\n",ans);
}
signed main() {
    mu[1]=1;
    for(int i=2;i<MAXN;++i) {
        if(!isc[i]) mu[i]=-1,primes.push_back(i);
        for(int p:primes) {
            if(i*p>=MAXN) break;
            isc[i*p]=true,mu[i*p]=-mu[i];
            if(i%p==0) { mu[i*p]=0; break; }
        }
    }
    for(int i=1;i<MAXN;++i) if(mu[i]!=0) Mu.push_back(i);
    for(int i=0;i<=10;++i) {
        C[i][0]=1;
        for(int j=1;j<=i;++j) C[i][j]=C[i-1][j]+C[i-1][j-1];
    }
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}

C. String Magic (Easy Version)

Problem Link

题目大意

给定长度为 \(n\) 的字符串 \(S\)，求有多少 \(p,k\) 满足 \(S[p,p+k-1]=S[p+k,p+2k-1]\) 且两个串均为回文。

数据访问：\(n\le 10^5\)。

思路分析

容易发现前一半与后一半相等的条件可以转化成 \(S[p,p+2k-1]\) 回文。

考虑枚举 \(i=p+k\)，求出以 \((i-1,i)\) 中间位置为回文中心的最远右端点 \(R_i\)，不妨假设 \(2\mid k\)，那么枚举 \(S[p+k,p+2k+1]\) 的回文中心 \((j-1,j)\)，容易发现 \((i,j)\) 合法当且仅当 \(2j-i-1\le R_i,j>i,R_j\ge 2j-i-1\)。

稍作变换，我们要求的就是 \(\left(i,\left\lfloor \dfrac{i+R_i+1}2\right\rfloor\right]\) 区间内满足 \(2j-R_j-1\le i\) 的数有几个，显然是一个二位偏序模型，直接主席树维护或离线后树状数组维护都可以，\(2\nmid k\) 的情况同理，写出对应的限制条件然后二位偏序即可。

时间复杂度 \(\mathcal O(n\log n)\)。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e5+5;
char str[MAXN],ss[MAXN<<1];
int rd[MAXN<<1];
class SegmentTree {
    private:
        struct Node {
            int ls,rs,cnt;
        }    tr[MAXN*30];
        inline void pushup(int p) { tr[p].cnt=tr[tr[p].ls].cnt+tr[tr[p].rs].cnt; }
        int siz;
    public:
        inline void Clear() { siz=0; }
        inline void Insert(int u,int l,int r,int q,int &p) {
            tr[p=++siz]={0,0,0};
            if(l==r) return tr[p].cnt=tr[q].cnt+1,void();
            int mid=(l+r)>>1;
            if(u<=mid) tr[p].rs=tr[q].rs,Insert(u,l,mid,tr[q].ls,tr[p].ls);
            else tr[p].ls=tr[q].ls,Insert(u,mid+1,r,tr[q].rs,tr[p].rs);
            pushup(p);
        }
        inline int Query(int ul,int ur,int l,int r,int q,int p) {
            if(ul<=l&&r<=ur) return tr[p].cnt-tr[q].cnt;
            int mid=(l+r)>>1,res=0;
            if(ul<=mid) res+=Query(ul,ur,l,mid,tr[q].ls,tr[p].ls);
            if(mid<ur) res+=Query(ul,ur,mid+1,r,tr[q].rs,tr[p].rs);
            return res;
        }
}    oddpal,evnpal;
int ot[MAXN],et[MAXN]; //odd and even
int oR[MAXN],eR[MAXN];
inline void solve() {
    oddpal.Clear(),evnpal.Clear();
    memset(rd,0,sizeof(rd));
    memset(ot,0,sizeof(ot));
    memset(et,0,sizeof(et));
    scanf("%s",str+1);
    int n=strlen(str+1),m=2*n+1;
    for(int i=1;i<=m;++i) ss[i]=(i%2==0)?(str[i/2]):'#';
    ss[0]='{',ss[2*n+2]='}';
    for(int i=1,l=0,r=0;i<=m;++i) {
        if(i<=r) rd[i]=min(r-i+1,rd[r+l-i]);
        while(ss[i+rd[i]]==ss[i-rd[i]]) ++rd[i];
        if(i+rd[i]-1>r) l=i-rd[i]+1,r=i+rd[i]-1; 
    }
    for(int i=1;i<=n;++i) { //odd palin(i)
        int rad=rd[2*i]/2;
        oR[i]=i+rad-1;
        oddpal.Insert(2*i-oR[i],0,n,ot[i-1],ot[i]);
    }
    for(int i=1;i<=n;++i) { //even palin(i-1,i)
        int rad=(rd[2*i-1]-1)/2;
        eR[i]=i+rad-1;
        evnpal.Insert(2*i-eR[i]-1,0,n,et[i-1],et[i]);
    }
    ll ans=0;
    for(int i=1;i<=n;++i) {
        ans+=oddpal.Query(0,i,0,n,ot[i-1],ot[(i+eR[i])/2]);
        if(eR[i]==i) continue;
        ans+=evnpal.Query(0,i,0,n,et[i],et[(i+eR[i]+1)/2]);
    }
    printf("%lld\n",ans);
}
signed main() {
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}

D. String Magic (Hard Version)

Problem Link

题目大意

给定长度为 \(n\) 的字符串 \(S\)，对 \(S\) 的每个前缀都求出上一问的答案。

数据访问：\(n\le 10^5\)。

思路分析

考虑右端点在 \(i\) 的串有多少个，用 PAM 维护插入 \(S_i\) 后的回文后缀，若没有新建本质不同回文后缀，直接用原来的答案即可，否则继承 \(fail\) 指针对应的更短后缀的答案，问题转化为判定某个 \((p,k)\) 是否合法，可以直接哈希，也可以在 PAM 上倍增看是否有长度恰好为 \(k/2\) 的串判断。

时间复杂度 \(\mathcal O(n\log n)\)。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e5+5;
char str[MAXN];
struct PAM {
    struct Node {
        int len,fail,son[26];
    }    tr[MAXN];
    int lst,tot;
    inline void init() {
        tr[0].len=0, tr[0].fail=1,memset(tr[0].son,0,sizeof(tr[0].son));
        tr[1].len=-1,tr[1].fail=0,memset(tr[1].son,0,sizeof(tr[1].son));
        tot=1,lst=0,str[0]='#';
    }
    inline int node(int len) {
        ++tot,tr[tot].len=len,tr[tot].fail=0;
        memset(tr[tot].son,0,sizeof(tr[tot].son));
        return tot;
    }
    inline int add(int i) {
        int c=str[i]-'a';
        auto get=[&](int x) {
            while(str[i]!=str[i-tr[x].len-1]) x=tr[x].fail;
            return x;
        };
        int p=get(lst);
        if(!tr[p].son[c]) {
            int q=node(tr[p].len+2);
            tr[q].fail=tr[get(tr[p].fail)].son[c];
            tr[p].son[c]=q;
        }
        return lst=tr[p].son[c];
    }
}    P;
int sum[MAXN],fa[MAXN][20];
bool vis[MAXN];
inline void solve() {
    memset(fa,0,sizeof(fa));
    memset(vis,false,sizeof(vis));
    memset(sum,0,sizeof(sum));
    scanf("%s",str+1);
    P.init();
    int n=strlen(str+1);
    ll ans=0;
    for(int i=1;i<=n;++i) {
        int p=P.add(i);
        if(!vis[p]) {
            auto fail=[&](int p) { return P.tr[p].fail; };
            auto len=[&](int p) { return P.tr[p].len; };
            sum[p]=sum[fail(p)],fa[p][0]=fail(p),vis[p]=true;
            for(int k=1;k<20;++k) fa[p][k]=fa[fa[p][k-1]][k-1];
            if(len(p)%2==0) {
                int u=p;
                for(int k=19;~k;--k) if(len(fa[u][k])>=len(p)/2) u=fa[u][k];
                if(len(u)==len(p)/2) ++sum[p];
            }
        }
        ans+=sum[p];
        printf("%lld ",ans);
    }
    puts("");
}
signed main() {
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}

E. Snake

Problem Link

题目大意

将 \(1\sim n\) 排到 \(m\) 个队列里，每个队列长度在 \([1,k]\) 之间，队列之间本质相同，但同一队列的元素先后顺序有影响，求方案数。

数据范围：\(n,m,k\le10^6\)。

思路分析

考虑构造形式幂级数，从 \(m=1\) 的情况入手，关于 \(n\) 的 EGF 就是 \(\hat F(x)=x^1+x^2+\cdots+x^k=\dfrac{x-x^{k+1}}{1-x}\)，答案即为 \(n![x^n]\hat F(x)\)。

然后考虑 \(m>1\) 的情况，根据 EGF 卷积的组合意义可以得到答案关于 \(n\) 的 EGF 就是 \(\dfrac 1{m!}\hat F^m(x)\)，因此答案为 \(\dfrac{n!}{m!}[x^n]\hat F^m(x)\)。

那么原问题就转化成了求 \([x^n](x-x^{k+1})^m\times (1-x)^{-m}\)，提出一个 \(x\) 得到 \([x^{n-m}](1-x^k)^m\times (1-x)^{-m}\)。

直接二项式定理拆开，其中 \((1-x)^{-m}\) 的 \(i\) 次项系数就是 \([x^i]=\binom{m+i-1}{m-1}\)，推式子得到：

\[\text{Answer}=\sum_{i=0}^{ik\le n-m} (-1)^i\binom mi\binom{n-ik-1}{m-1} \]

预处理组合数后直接算就行，注意特判 \(mk<n\) 的情况。

时间复杂度 \(\mathcal O(n)\)。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5,MOD=998244353;
inline int ksm(int a,int b=MOD-2,int p=MOD) {
    int ret=1;
    while(b) ret=(b&1?1ll*ret*a%p:ret),a=1ll*a*a%p,b=b>>1;
    return ret;
}
int fac[MAXN],inv[MAXN];
inline int binom(int n,int m) {
    if(m<0||m>n) return 0;
    return 1ll*fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
inline void solve() {
    int n,m,k,ans=0;
    scanf("%d%d%d",&n,&m,&k);
    if(1ll*m*k<n) return puts("0"),void();
    auto add=[&](int &x,int y) { x=(x+y>=MOD)?x+y-MOD:x+y; };
    auto sub=[&](int &x,int y) { x=(x>=y)?x-y:x+MOD-y; };
    for(int i=0;i<=m&&i*k<=n-m;++i) {
        if(i&1) sub(ans,1ll*binom(m,i)*binom(n-i*k-1,m-1)%MOD);
        else add(ans,1ll*binom(m,i)*binom(n-i*k-1,m-1)%MOD);
    }
    printf("%lld\n",1ll*ans*fac[n]%MOD*inv[m]%MOD);
}
signed main() {
    fac[0]=1;
    for(int i=1;i<MAXN;++i) fac[i]=1ll*fac[i-1]*i%MOD;
    inv[MAXN-1]=ksm(fac[MAXN-1]);
    for(int i=MAXN-1;i;--i) inv[i-1]=1ll*inv[i]*i%MOD;
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}

F. Touhou Red Red Blue

Problem Link

题目大意

顺次给你 \(n\) 个元素，和两个槽 \(A,B\) 初始为空，每个元素有一个颜色在 \(1\sim 3\) 之间，每当你拿到一个元素，你可以选择是否把这个元素保留，若保留：

\(A\) 为空放进 \(A\) 中。

否则若 \(B\) 为空放进 \(B\) 中。

否则：

若两个槽中和你手中的元素都同色，扔掉这三个元素，得 \(1\) 分，然后将 \(A\) 替换成一个任意的元素。

若两个槽中和你手中的元素两两异色，扔掉这三个元素，然后将 \(A,B\) 都替换成一个任意的元素。

否则扔掉 \(A\)，把 \(B\) 放到 \(A\) 上，把你手中的元素放到 \(B\) 上。

求出最大可能的得分。

数据范围：\(n\le10^5\)。

思路分析

直接 dp，状态里记录每个槽的状态然后模拟即可。

时间复杂度 \(\mathcal O(n)\)。

代码呈现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
mt19937 rnd(time(0));
const int MAXN=1e5+5;
int f[MAXN][4][4];
void upd(int &x,int y){x=max(x,y);}
void solve(){
    string s;cin>>s;
    int n=s.length();
    memset(f,-0x3f,sizeof(f));
    f[0][0][0]=0;
    for(int i=0;i<n;i++)
        for(int j:{0,1,2,3})
            for(int k:{0,1,2,3}) if(j>0||j==0&&k==0){
                int ch=(s[i]=='R'?1:(s[i]=='B'?2:3));
                upd(f[i+1][j][k],f[i][j][k]);
                if(j==k&&k==ch){
                    for(int t:{0,1,2,3}) upd(f[i+1][t][0],f[i][j][k]+1);
                }
                if(j&&k&&j!=k&&k!=ch&&ch!=j){
                    for(int t:{0,1,2,3})
                    for(int l:{0,1,2,3}) upd(f[i+1][t][l],f[i][j][k]);
                }
                if(j&&k){
                    upd(f[i+1][k][ch],f[i][j][k]);
                }
                if(!j) upd(f[i+1][ch][0],f[i][j][k]);
                else if(!k) upd(f[i+1][j][ch],f[i][j][k]);
            }
    int ans=0;
    for(int i=1;i<=n;i++)
        for(int j:{0,1,2,3}) for(int k:{0,1,2,3}) ans=max(ans,f[i][j][k]);
    cout<<ans<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    int _;cin>>_;
    while(_--) solve();
}

G. Expectation (Easy Version)

Problem Link

题目大意

给一个初始为 \(0\) 的随机变量 \(x\)，有 \(n\) 轮操作，每轮有 \(p\) 的概率使 \(x\) 变成 \(x+1\)。

给定 \(m\)，求 \(\sum_{i=1}^x i^m\) 的期望。

数据范围：\(n\le 10^6,m\le 10^9\)。

思路分析

设 \(S(x)=\sum_{i=1}^x i^m\)，直接列式求 \(x=i\) 的概率得到 \(\mathrm{Answer}=\sum_{i=0}^n S(i)\times p^i\times (1-p)^{n-i}\times \binom ni\)，直接计算即可。

时间复杂度 \(\mathcal O(n\log m)\)。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5,MOD=998244353;
inline int ksm(int a,int b=MOD-2,int p=MOD) {
    int ret=1;
    while(b) ret=(b&1?1ll*ret*a%p:ret),a=1ll*a*a%p,b=b>>1;
    return ret;
}
int fac[MAXN],inv[MAXN],P[MAXN],Q[MAXN];
inline void solve() {
    int n,m,a,b,ans=0;
    scanf("%d%d%d%d",&n,&m,&a,&b);
    int p=1ll*a*ksm(b)%MOD,q=(1+MOD-p)%MOD;
    for(int i=P[0]=Q[0]=1;i<=n;++i) P[i]=1ll*P[i-1]*p%MOD,Q[i]=1ll*Q[i-1]*q%MOD;
    for(int k=1,f=0;k<=n;++k) {
        f=(f+ksm(k,m))%MOD;
        ans=(ans+1ll*f*P[k]%MOD*Q[n-k]%MOD*fac[n]%MOD*inv[k]%MOD*inv[n-k]%MOD)%MOD;
    }
    printf("%d\n",ans);
}
signed main() {
    for(int i=fac[0]=inv[0]=1;i<MAXN;++i) inv[i]=ksm(fac[i]=1ll*i*fac[i-1]%MOD);
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}

H. Expectation (Hard Version)

Problem Link

题目大意

给一个初始为 \(0\) 的随机变量 \(x\)，有 \(n\) 轮操作，每轮有 \(p\) 的概率使 \(x\) 变成 \(x+1\)。

给定 \(m\)，求 \(\sum_{i=1}^x i^m\) 的期望。

数据范围：\(n\le 10^9,m\le 10^6\)。

思路分析

依然写出上式，考虑用下降幂和第二类斯特林数表示 \(i^m\)，稍作变换得到：

\[\begin{aligned} \mathrm{Answer} &=\sum_{i=0}^n \binom nip^i(1-p)^{n-i}\sum_{j=1}^i j^m\\[2ex] &=\sum_{j=1}^i j^m\sum_{i=0}^n\binom nip^i(1-p)^{n-i}\\[2ex] &=\sum_{j=1}^i\sum_{k=0}^m \begin{Bmatrix}m\\k\end{Bmatrix}\dfrac{m!}{(m-k)!}\sum_{i=0}^n\binom nip^i(1-p)^{n-i}\\[2ex] &=\sum_{k=0}^m\begin{Bmatrix}m\\k\end{Bmatrix}k!\sum_{i=k}^n\binom nip^i(1-p)^{n-i}\sum_{j=k}^i\binom{j}{k}\\[2ex] &=\sum_{k=0}^m\begin{Bmatrix}m\\k\end{Bmatrix}k!\sum_{i=k}^n\binom nip^i(1-p)^{n-i}\sum_{j=k}^i\binom{j+1}{k+1}-\binom{j}{k+1}\\[2ex] &=\sum_{k=0}^m\begin{Bmatrix}m\\k\end{Bmatrix}k!\sum_{i=k}^n\binom nip^i(1-p)^{n-i}\binom{i+1}{k+1}\\[2ex] &=\sum_{k=0}^m\begin{Bmatrix}m\\k\end{Bmatrix}k!\left(\sum_{i=k}^np^i(1-p)^{n-i}\binom ni\binom{i}{k+1}+\sum_{i=k}^np^i(1-p)^{n-i}\binom ni\binom{i}{k}\right)\\[2ex] &=\sum_{k=0}^m\begin{Bmatrix}m\\k\end{Bmatrix}k!\left(\binom{n}{k+1}\sum_{i=k}^np^i(1-p)^{n-i}\binom{n-k-1}{i-k-1}+\binom nk\sum_{i=k}^np^i(1-p)^{n-i}\binom{n-k}{i-k}\right)\\[2ex] &=\sum_{k=0}^m\begin{Bmatrix}m\\k\end{Bmatrix}k!\left(\binom{n}{k+1}p^{k+1}+\binom nkp^k\right)\\[2ex]\\ \end{aligned} \]

最后两行之间省略的过程见下：

\[\sum_{i=k}^np^i(1-p)^{n-i}\binom{n-k}{i-k}=\sum_{t=0}^{n-k}p^{t+k}(1-p)^{n-k-t}\binom{n-k}{t}=p^k(p+(1-p))^{n-k}=p^k \]

另一个求和式也是同理可以化简，因此只需要求出斯特林数的第 \(m\) 行元素即可，可以用一个简单的容斥处理：

\[\begin{aligned} \begin{Bmatrix}m\\k\end{Bmatrix} &=\dfrac 1{k!}\sum_{i=0}^k\binom ki(-1)^i(k-i)^m\\ &=\sum_{i=0}^k\dfrac{(-1)^i}{i!}\times\dfrac{(k-i)^m}{(k-i)!} \end{aligned} \]

一遍 NTT 即可求出，然后根据上式计算答案即可。

时间复杂度 \(\mathcal O(m\log m)\)。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=(1<<21)+5,MOD=998244353,INV=(MOD+1)/3;
inline int ksm(int a,int b=MOD-2,int m=MOD) {
    int ret=1;
    while(b) {
        if(b&1) ret=1ll*ret*a%m;
        a=1ll*a*a%m;
        b=b>>1;
    }
    return ret;
}
int rev[MAXN];
inline void NTT(int *f,int len,int op) {
    for(int i=0;i<len;++i) if(i<rev[i]) swap(f[i],f[rev[i]]);
    for(int s=2;s<=len;s=s<<1) {
        int u=ksm(op==1?3:INV,(MOD-1)/s);
        for(int i=0;i<len;i+=s) {
            for(int j=i,w=1;j<i+s/2;++j) {
                int x=f[j],y=1ll*w*f[j+s/2]%MOD;
                f[j]=(x+y>=MOD)?x+y-MOD:x+y;
                f[j+s/2]=(x>=y)?x-y:x+MOD-y;
                w=1ll*w*u%MOD;
            }
        }
    }
    if(op==-1) {
        int inv=ksm(len);
        for(int i=0;i<len;++i) f[i]=1ll*f[i]*inv%MOD;
    }
}
int fac[MAXN],inv[MAXN],binom[MAXN];
int F[MAXN],S[MAXN];
inline void solve() {
    int n,m,a,b,p,ans=0;
    scanf("%d%d%d%d",&n,&m,&a,&b),p=1ll*a*ksm(b)%MOD;
    int lim=1<<(__lg(m*2)+1);
    memset(S,0,sizeof(S)),memset(F,0,sizeof(F));
    for(int i=0;i<=m;++i) S[i]=1ll*ksm(i,m)*inv[i]%MOD;
    for(int i=0;i<=m;++i) F[i]=i&1?MOD-inv[i]:inv[i];
    for(int i=0;i<lim;++i) {
        rev[i]=(rev[i>>1]>>1);
        if(i&1) rev[i]|=lim>>1;
    }
    NTT(S,lim,1),NTT(F,lim,1);
    for(int i=0;i<lim;++i) S[i]=1ll*S[i]*F[i]%MOD;
    NTT(S,lim,-1);
    memset(binom,0,sizeof(binom)),binom[0]=1;
    for(int i=1;i<=min(m+1,n);++i) binom[i]=1ll*binom[i-1]*(n-i+1)%MOD;
    for(int i=0;i<=min(m+1,n);++i) binom[i]=1ll*binom[i]*inv[i]%MOD;
    for(int k=0;k<=m;++k) {
        int tmp=(1ll*binom[k]*ksm(p,k)%MOD+1ll*binom[k+1]*ksm(p,k+1)%MOD)%MOD;
        ans=(ans+1ll*S[k]*fac[k]%MOD*tmp%MOD)%MOD;
    }
    printf("%d\n",ans);
}
signed main() {
    fac[0]=1;
    for(int i=1;i<MAXN;++i) fac[i]=1ll*fac[i-1]*i%MOD;
    inv[MAXN-1]=ksm(fac[MAXN-1]);
    for(int i=MAXN-1;i;--i) inv[i-1]=1ll*inv[i]*i%MOD;
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}

I. Tree

Problem Link

题目大意

给定一棵 \(n\) 个点的树以及一种树链剖分方式，要求对每条链建线段树，树根接在链顶的父亲上，求新树的最大深度。

数据范围：\(n\le 10^6\)。

思路分析

注意到每个节点线段树上对应的深度是可以 \(\mathcal O(1)\) 计算的，因此直接模拟求出每个点的深度即可。

时间复杂度 \(\mathcal O(n)\)。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+100;
inline char gc(){
    static char buf[N],*p1=buf,*p2=buf;
    if(p1==p2){
        p2=(p1=buf)+fread(buf,1,N,stdin);
    }
    return *p1++;
}
inline int read(){
    int x=0;char c=gc();
    for(;c<'0'||c>'9';c=gc());
    for(;c>='0'&&c<='9';c=gc())x=x*10+c-48;
    return x;
}
int n;
int pre[N];
int hd[N],to[N],nxt[N],ec;
void ae(int u,int v){
    ++ec;
    to[ec]=v;
    nxt[ec]=hd[u];
    hd[u]=ec;
}
int wson[N],dep[N];
int chsiz[N];
void dfs1(int u,int t){
    chsiz[t]++;
    for(int e=hd[u];e;e=nxt[e]){
        int v=to[e];
        dfs1(v,v==wson[u]?t:v);
    }
}
void dfs2(int u,int t,int f){
    if(u==t){
        dep[u]=dep[f]+pre[chsiz[u]];
    }else{
        dep[u]=dep[t];
    }
    for(int e=hd[u];e;e=nxt[e]){
        int v=to[e];
        dfs2(v,v==wson[u]?t:v,u);
    }
}
void solve(){
    n=read();
    ec=0;
    memset(hd,0,sizeof(hd));
    memset(chsiz,0,sizeof(chsiz));
    int rt=0;
    for(int i=1;i<=n;i++){
        int f=read();
        ae(f,i);
        if(f==0){
            rt=i;
        }
    }
    for(int i=1;i<=n;i++){
        wson[i]=read();
    }
    dep[rt]=0;
    dfs1(rt,rt);
    dfs2(rt,rt,rt);
    int ans=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,dep[i]);
    }
    printf("%d\n",ans);
    return;
}
int main(){
    for(int i=1,j=0;i<N;i++){
        while((1<<j)<i) j++;
        pre[i]=j+1;
    }
    int ttt=read();
    while(ttt--){
        solve();
    }
    return 0;
}

J. Cut The Tree

Problem Link

题目大意

给一棵 \(n\) 个节点的树，节点带权 \(a_i\)。

对于每个 \(u\)，定义 \(\mathrm{in}(u)\) 表示 \(u\) 子树内最大的一对 \(a_i\oplus a_j\)，\(\mathrm{out}(u)\) 表示 \(u\) 子树外最大的一对 \(a_i\oplus a_j\)。

求出最小的 \(|\mathrm{in}(u)-\mathrm{out}(u)|\)。

数据范围：\(n\le 2\times 10^5,V=\max\{a_i\}\le 10^9\)。

思路分析

首先考虑 \(\mathrm{in}(u)\)，直接 dsu on tree，每次继承重儿子得到的 01Trie 和答案，然后插入轻子树中的元素，时间复杂度 \(\mathcal O(n\log n\log V)\)。

然后考虑 \(\mathrm{out}(u)\)，先观察全局的最大异或对 \(p,q\)，对于任意一个不在 \(p\to 1\) 或 \(q\to 1\) 上的 \(u\)，\(\mathrm{out}(u)\) 就等于 \(a_p\oplus a_q\)，剩下的就是 \(1\to p\) 和 \(1\to q\) 上的点，从深到浅暴力枚举，每次插入当前节点的其他子树即可，每条链处理复杂度都是 \(\mathcal O(n\log V)\) 的。

分别处理，最后计算答案即可。

时间复杂度 \(\mathcal O(n\log n\log V)\)。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5,inf=2e9;
typedef array<int,2> Pair;
struct Trie {
    int ans,tot;
    Pair vers;
    struct Node { Pair ch; int idx; } tr[MAXN*32];
    inline void init() {
        for(int i=0;i<=tot;++i) tr[i]={{0,0},0};
        ans=0,tot=0,vers={-1,-1};
    }
    inline void insert(int idx,int val) {
        int res=0,p=0;
        for(int k=31;~k;--k) {
            int x=(val>>k)&1;
            if(!tr[p].ch[x]) tr[p].ch[x]=++tot;
            p=tr[p].ch[x];
        }
        tr[p].idx=idx;
        p=0;
        for(int k=31;~k;--k) {
            int x=(val>>k)&1;
            if(tr[p].ch[x^1]) res|=1ll<<k,p=tr[p].ch[x^1];
            else p=tr[p].ch[x];
        }
        if(res>ans) ans=res,vers={idx,tr[p].idx};
    }
}    Trie;
int fa[MAXN],a[MAXN],out[MAXN],in[MAXN];
vector <int> G[MAXN];
int dfn[MAXN],rnk[MAXN],dcnt=0,siz[MAXN],hson[MAXN];
inline void dfs0(int u,int Fa) {
    fa[u]=Fa,rnk[dfn[u]=++dcnt]=u,siz[u]=1;
    for(int v:G[u]) if(v^Fa) {
        dfs0(v,u),siz[u]+=siz[v];
        if(siz[hson[u]]<siz[v]) hson[u]=v;
    }
}
inline void dfs1(int u) {
    for(int v:G[u]) if(v!=fa[u]&&v!=hson[u]) {
        dfs1(v),Trie.init();
    }
    if(hson[u]) dfs1(hson[u]);
    Trie.insert(u,a[u]);
    for(int v:G[u]) if(v!=fa[u]&&v!=hson[u]) {
        for(int x=dfn[v];x<dfn[v]+siz[v];++x) Trie.insert(rnk[x],a[rnk[x]]);
    }
    in[u]=Trie.ans;
}
inline void solve() {
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i) G[i].clear(),hson[i]=0;
    Trie.init();
    for(int i=1;i<=n;++i) scanf("%d",&a[i]),Trie.insert(i,a[i]);
    for(int i=1;i<=n;++i) out[i]=Trie.ans;
    for(int i=1,u,v;i<n;++i) {
        scanf("%d%d",&u,&v);
        G[u].push_back(v),G[v].push_back(u);
    }
    dcnt=0,dfs0(1,0);
    Pair vers=Trie.vers;
    for(int t:{0,1}) {
        int p=vers[t];
        Trie.init();
        vector <int> ci;
        for(int u=p;u!=1;u=fa[u]) ci.push_back(u);
        ci.push_back(1),reverse(ci.begin(),ci.end());
        for(int i=0;i<(int)ci.size();++i) {
            int u=ci[i];
            if(u>1) out[u]=Trie.ans;
            if(u==p) break;
            Trie.insert(u,a[u]);
            for(int v:G[u]) if(v!=ci[i+1]&&v!=fa[u]) {
                for(int x=dfn[v];x<dfn[v]+siz[v];++x) Trie.insert(rnk[x],a[rnk[x]]);
            }
        }
    }
    out[1]=0,Trie.init();
    dfs1(1);
    int ans=inf;
    for(int i=2;i<=n;++i) ans=min(ans,abs(in[i]-out[i]));
    printf("%d\n",ans);
}
signed main() {
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}

K. Cactus Circuit

Problem Link

题目大意

给一个 \(n\) 个点的仙人掌，每条边可以持续运行 \(t(e)\) 的时间，你要指定每条边开始运行的时间，使得任何时候这个仙人掌都是联通的。

数据范围：\(n\le 10^5\)。

思路分析

考虑每个环，显然只能是先断掉一条边，等有边无法运行时再加入，求出前三小的 \(t(e)\)，记为 \(t_1,t_2,t_3\)，可以证明最优解一定是断掉 \(t_1\) 或 \(t_2\)，此时代价是 \(\min(t_1+t_2,t_3)\)，否则运行时间一定不超过 \(t_2\)。

对每个环暴力考虑，可以先建一棵生成树，对于非树边暴力跳 LCA 并统计信息即可，也可以用 tarjan 来缩点，答案最后记得和非环边取 \(\min\)。

时间复杂度 \(\mathcal O(n)\)。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5,inf=2e9;
struct Edge { int u,v,w; };
int dsu[MAXN];
inline int find(int x) { while(x^dsu[x]) x=dsu[x]=dsu[dsu[x]]; return x; }
vector <Edge> G[MAXN];
int Fa[MAXN],dep[MAXN],wt[MAXN];
bool mark[MAXN];
inline void dfs(int u,int fa) {
    dep[u]=dep[fa]+1;
    for(auto e:G[u]) if(e.v^fa) Fa[e.v]=u,wt[e.v]=e.w,dfs(e.v,u);
}
inline void solve() {
    int n,m;
    cin>>n>>m;
    vector <Edge> cyc;
    for(int i=1;i<=n;++i) G[i].clear(),Fa[i]=dep[i]=wt[i]=mark[i]=0,dsu[i]=i;
    for(int i=1,u,v,w;i<=m;++i) {
        cin>>u>>v>>w;
        int x=find(u),y=find(v);
        if(x==y) cyc.push_back({u,v,w});
        else {
            G[u].push_back({u,v,w});
            G[v].push_back({v,u,w});
            dsu[x]=y;
        }
    }
    dfs(1,0);
    int ans=inf;
    for(auto e:cyc) {
        array <int,3> val={e.w,inf,inf};
        auto add=[&](int w) {
            val[2]=min(val[2],max(w,val[1]));
            val[1]=min(val[1],max(w,val[0]));
            val[0]=min(val[0],w);
        };
        for(int u=e.u,v=e.v;u!=v;) {
            if(dep[u]<dep[v]) swap(u,v);
            assert(!mark[u]);
            add(wt[u]),mark[u]=true,u=Fa[u];
        }
        ans=min({ans,val[0]+val[1],val[2]});
    }
    for(int i=2;i<=n;++i) if(!mark[i]) ans=min(ans,wt[i]);
    cout<<ans<<"\n";
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int T; cin>>T;
    while(T--) solve();
    return 0;
}

L. Counting Stars

Problem Link

题目大意

给定 \(n\) 个点 \(m\) 条边的无向图，定义 \(f(k)\) 表示图中有多少个 \(k\) 条边的菊花，求 \(f(2)\oplus f(3)\oplus\cdots\oplus f(n-1)\)。

数据范围：\(n,m\le 10^6\)。

思路分析

对于某个点 \(u\) 对 \(f(k)\) 的贡献就是 \(\binom{\mathrm{deg}(u)}k\)，枚举 \((1,\mathrm{deg}(u)]\) 的每个 \(k\) 暴力算即可，复杂度是 \(\mathcal O(\sum \mathrm{deg}(u))=\mathcal O(m)\) 的。

时间复杂度 \(\mathcal O(n+m)\)。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5,MOD=1e9+7;
inline int ksm(int a,int b=MOD-2,int p=MOD) {
    int ret=1;
    while(b) ret=(b&1?1ll*ret*a%p:ret),a=1ll*a*a%p,b=b>>1;
    return ret;
}
int ans[MAXN],deg[MAXN],fac[MAXN],inv[MAXN];
inline int binom(int n,int m) {
    if(m<0||m>n) return 0;
    return 1ll*fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
inline void solve() {
    int n,m;
    cin>>n>>m; 
    memset(ans,0,sizeof(ans)),memset(deg,0,sizeof(deg));
    for(int u,v;m--;) cin>>u>>v,++deg[u],++deg[v];
    for(int i=1;i<=n;++i) {
        auto add=[&](int &x,int y) { x=(x+y>=MOD)?x+y-MOD:x+y; };
        for(int j=2;j<=deg[i];++j) add(ans[j],binom(deg[i],j));
    }
    int res=0;
    for(int i=2;i<n;++i) res^=ans[i];
    cout<<res<<"\n";
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    fac[0]=1;
    for(int i=1;i<MAXN;++i) fac[i]=1ll*fac[i-1]*i%MOD;
    inv[MAXN-1]=ksm(fac[MAXN-1]);
    for(int i=MAXN-1;i;--i) inv[i-1]=1ll*inv[i]*i%MOD;
    int T; cin>>T;
    while(T--) solve(); 
}