AGC038 部分题解

Author： RainAir
发布时间：November 20, 2020
1275views
One comment
3957 words
Categories：题解

E

题意

有一个随机数生成器，生成 $[0,n-1]$ 之内的数，生成第 $i$ 个数的概率为 $\frac{A_i}{S}$，其中 $S=\sum_{i=1}^n A_i$。

当 $\forall i \in [0,n-1]$ $i$ 被生成至少 $B_i$ 次时停止生成，求期望生成次数，对大质数取模。

题解

设第 $i$ 个数最后一次被随机到的时间为 $t_i$，答案就是 $\max t_i$ 的期望。

限制所有都要完成一般都不好做，考虑 $min-max$ 容斥变成枚举一个集合 $S$ ，求 $\min_{i \in S} t_i$ 的期望。

枚举集合后，问题变成求存在 $S$ 内某一个元素被随机 $b_i$ 次这个事件发生的期望时间。我们发现这样还是有可能随机到 $S$ 外的元素的，一个经典套路是算出期望多少次能操作一次 $S$ 内的元素，然后转化为只考虑 $S$ 内元素操作的问题，最后乘上去即可。可以发现这个期望次数为 $\frac{\sum_{i=1}^n A_i}{\sum_{i \in S} A_i}$。

现在问题在于给定一个集合 $S$ ，在 $S$ 内随机，求存在一个数满足条件的期望时间。首先根据：

$$ \sum_{i \geq 0} P[X=i]i = \sum_{i \geq 0} P[X \geq i] $$

可以得到，我们只需要对于每个时间 $T$ 求出在 $T$ 时间还没结束的概率，求和即可。

我们考虑如何暴力的计算：先枚举在时间 $T$ 结束，接下来枚举序列 $b_i$ 表示集合中元素 $i$ 被随机到的次数，需要满足 $\forall i \in S,b_i < B_i$，$\sum_{i \in S} b_i = T$，这样一个序列的概率就是 $\prod_{i \in T} (\frac{A_i}{\sum_{i \in S} A_i})^{b_i}\frac{T!}{\prod_{i \in S} b_i!}$。

所以答案是：

$$ \sum_{S \subseteq [n],S \neq \emptyset} (-1)^{|S|-1}\frac{\sum_{i=1}^n A_i}{\sum_{i \in S} A_i} \sum_{T=0}^{\sum_{i \in S} (b_i-1) + 1} \sum_{\{b\},\sum_{i \in S} b_i = T} \prod_{i \in T} (\frac{A_i}{\sum_{i \in S} A_i})^{b_i}\frac{T!}{\prod_{i \in S} b_i!} $$

稍加整理可得

$$ \sum_{S \subseteq [n],S \neq \emptyset} (-1)^{|S|-1} \frac{\sum_{i=1}^n A_i}{\sum_{i \in S} A_i} \sum_{T=0}^{\sum_{i \in S} (b_i-1) + 1} T!(\frac{1}{\sum_{i \in S} A_i})^T \sum_{\{b\},\sum_{i \in S} b_i = T} \prod_{i \in S} \frac{A_i^{b_i}}{b_i!} $$

于是可以考虑对这个 dp：发现最终答案系数只和 $\sum b_i,\sum A_i$ 有关，我们带着容斥系数 dp，设 $f_{i,j,k}$ 表示考虑前 $i$ 个数，$\sum b_i = j,\sum A_i = k$ 的答案，转移的时候枚举这个位置选或者不选，选的话枚举 $b_i$ 是多少，可以得到转移式子：

$$ f_{i,j,k} = f_{i-1,j,k}-\sum_{x=0}^{B_i-1}\frac{A_i^x}{x!} f_{i-1,j-A_i,k-x} $$

然后最后把应该乘的系数乘上去就好了。

假设 $n,\sum A,\sum B$ 同阶，看起来时间复杂度是 $O(n^4)$ 的，但是实际分析一下：复杂度是：

$$ \begin{aligned} \sum_{i=1}^n \sum_{j=0}^{\sum A_i} \sum_{k=0}^{\sum B_i } \sum_{l=0}^{B_i-1} 1 &= \sum_{i=1}^n \sum_{l=0}^{B_i-1} (\sum A_i) (\sum B_i)\\ &=(\sum A_i)(\sum B_i)^2 \\ &= O(n^3) \end{aligned} $$

所以可以通过此题。代码可能和博客定义的是反的，感性理解一下（

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 400+5;
const int ha = 998244353;
int n,a[MAXN],b[MAXN];
int f[MAXN][MAXN];
int sma,smb;

inline void add(int &x,int y){
    x += y-ha;x += x>>31&ha;
}

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

int fac[MAXN],inv[MAXN];

int main(){
    fac[0] = 1;FOR(i,1,MAXN-1) fac[i] = 1ll*fac[i-1]*i%ha;
    inv[MAXN-1] = qpow(fac[MAXN-1]);ROF(i,MAXN-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha;
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d%d",a+i,b+i);
    FOR(i,1,n) sma += a[i],smb += b[i]-1;
    f[0][0] = -1;
    FOR(i,1,n){
        ROF(j,sma,a[i]){
            ROF(k,smb,0){
                ROF(x,std::min(k,b[i]-1),0){
                    add(f[j][k],(ha-1ll*f[j-a[i]][k-x]*inv[x]%ha*qpow(a[i],x)%ha)%ha);
                }
            }
        }
    }
    int ans = 0;
    FOR(j,0,sma) FOR(k,0,smb){
        int gx = f[j][k];
        gx = 1ll*gx*fac[k]%ha*sma%ha;
        gx = 1ll*gx*qpow(qpow(j,k+1))%ha;
        add(ans,gx);
    }
    printf("%d\n",ans);
    return 0;
}

F

题意

给定两个长度为 $n$ 的排列 $P,Q$，要求你构造两个长度为 $n$ 的排列 $A,B$，满足：

$A_i$ 取值 $\{i,P_i\}$
$B_i$ 取值 $\{i,Q_i\}$

要求 $A,B$ 不同的位置尽量多，求出这个最多的位置个数。

题解

将 $P,Q$ 分成若干个环，同一个环要么都取 $i$ 要么都取 $P_i/Q_i$。

讨论一下 $P_i,Q_i$ 之间的关系，可以得到以下情况：

$P_i=Q_i=i$：无论如何都相等。
$P_i,Q_i \neq i,P_i \neq Q_i$：同时不转相等。
$P_i=i,Q_i \neq i$：$B_i$ 不转相等。
$P_i \neq i,Q_i = i$：$A_i$ 不转相等。
$P_i=Q_i,P_i,Q_i \neq i$：同时转相等。

网络流。把 $B$ 倒过来就行了。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 2e5 + 5;

struct Edge{
    int to,w,nxt;
}e[MAXN<<4];
int head[MAXN],cnt=1,cur[MAXN],dep[MAXN];

inline void add(int u,int v,int w){
    e[++cnt] = (Edge){v,w,head[u]};head[u] = cnt;
    e[++cnt] = (Edge){u,0,head[v]};head[v] = cnt;
}

int S,T,N;

inline bool bfs(){
    FOR(i,0,N) cur[i] = head[i],dep[i] = 0;
    std::queue<int> q;q.push(S);dep[S] = 1;
    while(!q.empty()){
        int v = q.front();q.pop();
        for(int i = head[v];i;i = e[i].nxt){
            if(e[i].w > 0 && !dep[e[i].to]){
                dep[e[i].to] = dep[v]+1;
                q.push(e[i].to);
            }
        }
    }
    return dep[T];
}

inline int dfs(int v,int lim=1e9){
    if(v == T) return lim;
    if(!lim) return 0;
    int ans = 0;
    for(int &i = cur[v];i;i = e[i].nxt){
        if(e[i].w > 0 && dep[e[i].to] == dep[v]+1){
            int t = dfs(e[i].to,std::min(lim,e[i].w));
            if(t > 0){
                ans += t;
                e[i].w -= t;
                e[i^1].w += t;
                lim -= t;
                if(!lim) break;
            }
        }
    }
    return ans;
}

inline int Dinic(){
    int ans = 0,flow;
    while(bfs()) while((flow=dfs(S))) ans += flow;
    return ans;
}

int n,p[MAXN],q[MAXN];
bool vis[MAXN];
int belp[MAXN],belq[MAXN];

inline void dfs(int v,int now,int p[],int bel[]){
    vis[v] = 1;bel[v] = now;
    if(vis[p[v]]) return;
    dfs(p[v],now,p,bel);
}

int main(){
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",p+i),++p[i];
    FOR(i,1,n) scanf("%d",q+i),++q[i];
    FOR(i,1,n) if(!vis[i]) ++N,dfs(i,N,p,belp);
    FOR(i,1,n) vis[i] = 0;
    FOR(i,1,n) if(!vis[i]) ++N,dfs(i,N,q,belq);
    S = N+1;T = N+2;N = T;
    int ans = n;
    FOR(i,1,n){
        if(p[i] == q[i]){
            if(p[i] == i){
                ans--;continue;
            }
            else{
                add(belp[i],belq[i],1);
                add(belq[i],belp[i],1);
            }
        }
        else{
            if(p[i] == i && q[i] != i){
                add(belq[i],T,1);
            }
            else if(p[i] != i && q[i] == i){
                add(S,belp[i],1);
            }
            else{
                add(belq[i],belp[i],1);
            }
        }
    }
    printf("%d\n",ans-Dinic());
    return 0;
}
/*
p: 割左边=不转 右边=转
q反过来 
何时答案会-1:
p[i]=q[i]=i 无论如何都会-1
p[i],q[i] != i 同时不转
p[i]=i,q[i]!=i 2不转
p[i]!=i,q[i]=i 1不转
p[i]=q[i],p[i],q[i]!=i  同时转
*/

Last modification：November 20th, 2020 at 06:05 pm

如果觉得我的文章对你有用，请随意赞赏

One comment

orz
November 22nd, 2020 at 06:11 pm

orz

Reply

AGC038 部分题解

RainAir • 2020 年 11 月 20 日

E

题意

有一个随机数生成器，生成 $[0,n-1]$ 之内的数，生成第 $i$ 个数的概率为 $\frac{A_i}{S}$，其中 $S=\sum_{i=1}^n A_i$。

当 $\forall i \in [0,n-1]$ $i$ 被生成至少 $B_i$ 次时停止生成，求期望生成次数，对大质数取模。

题解

设第 $i$ 个数最后一次被随机到的时间为 $t_i$，答案就是 $\max t_i$ 的期望。

限制所有都要完成一般都不好做，考虑 $min-max$ 容斥变成枚举一个集合 $S$ ，求 $\min_{i \in S} t_i$ 的期望。

现在问题在于给定一个集合 $S$ ，在 $S$ 内随机，求存在一个数满足条件的期望时间。首先根据：

$$ \sum_{i \geq 0} P[X=i]i = \sum_{i \geq 0} P[X \geq i] $$

可以得到，我们只需要对于每个时间 $T$ 求出在 $T$ 时间还没结束的概率，求和即可。

所以答案是：

稍加整理可得

$$ f_{i,j,k} = f_{i-1,j,k}-\sum_{x=0}^{B_i-1}\frac{A_i^x}{x!} f_{i-1,j-A_i,k-x} $$

然后最后把应该乘的系数乘上去就好了。

假设 $n,\sum A,\sum B$ 同阶，看起来时间复杂度是 $O(n^4)$ 的，但是实际分析一下：复杂度是：

所以可以通过此题。代码可能和博客定义的是反的，感性理解一下（

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 400+5;
const int ha = 998244353;
int n,a[MAXN],b[MAXN];
int f[MAXN][MAXN];
int sma,smb;

inline void add(int &x,int y){
    x += y-ha;x += x>>31&ha;
}

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

int fac[MAXN],inv[MAXN];

int main(){
    fac[0] = 1;FOR(i,1,MAXN-1) fac[i] = 1ll*fac[i-1]*i%ha;
    inv[MAXN-1] = qpow(fac[MAXN-1]);ROF(i,MAXN-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha;
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d%d",a+i,b+i);
    FOR(i,1,n) sma += a[i],smb += b[i]-1;
    f[0][0] = -1;
    FOR(i,1,n){
        ROF(j,sma,a[i]){
            ROF(k,smb,0){
                ROF(x,std::min(k,b[i]-1),0){
                    add(f[j][k],(ha-1ll*f[j-a[i]][k-x]*inv[x]%ha*qpow(a[i],x)%ha)%ha);
                }
            }
        }
    }
    int ans = 0;
    FOR(j,0,sma) FOR(k,0,smb){
        int gx = f[j][k];
        gx = 1ll*gx*fac[k]%ha*sma%ha;
        gx = 1ll*gx*qpow(qpow(j,k+1))%ha;
        add(ans,gx);
    }
    printf("%d\n",ans);
    return 0;
}

F

题意

给定两个长度为 $n$ 的排列 $P,Q$，要求你构造两个长度为 $n$ 的排列 $A,B$，满足：

$A_i$ 取值 $\{i,P_i\}$
$B_i$ 取值 $\{i,Q_i\}$

要求 $A,B$ 不同的位置尽量多，求出这个最多的位置个数。

题解

将 $P,Q$ 分成若干个环，同一个环要么都取 $i$ 要么都取 $P_i/Q_i$。

讨论一下 $P_i,Q_i$ 之间的关系，可以得到以下情况：

$P_i=Q_i=i$：无论如何都相等。
$P_i,Q_i \neq i,P_i \neq Q_i$：同时不转相等。
$P_i=i,Q_i \neq i$：$B_i$ 不转相等。
$P_i \neq i,Q_i = i$：$A_i$ 不转相等。
$P_i=Q_i,P_i,Q_i \neq i$：同时转相等。

网络流。把 $B$ 倒过来就行了。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 2e5 + 5;

struct Edge{
    int to,w,nxt;
}e[MAXN<<4];
int head[MAXN],cnt=1,cur[MAXN],dep[MAXN];

inline void add(int u,int v,int w){
    e[++cnt] = (Edge){v,w,head[u]};head[u] = cnt;
    e[++cnt] = (Edge){u,0,head[v]};head[v] = cnt;
}

int S,T,N;

inline bool bfs(){
    FOR(i,0,N) cur[i] = head[i],dep[i] = 0;
    std::queue<int> q;q.push(S);dep[S] = 1;
    while(!q.empty()){
        int v = q.front();q.pop();
        for(int i = head[v];i;i = e[i].nxt){
            if(e[i].w > 0 && !dep[e[i].to]){
                dep[e[i].to] = dep[v]+1;
                q.push(e[i].to);
            }
        }
    }
    return dep[T];
}

inline int dfs(int v,int lim=1e9){
    if(v == T) return lim;
    if(!lim) return 0;
    int ans = 0;
    for(int &i = cur[v];i;i = e[i].nxt){
        if(e[i].w > 0 && dep[e[i].to] == dep[v]+1){
            int t = dfs(e[i].to,std::min(lim,e[i].w));
            if(t > 0){
                ans += t;
                e[i].w -= t;
                e[i^1].w += t;
                lim -= t;
                if(!lim) break;
            }
        }
    }
    return ans;
}

inline int Dinic(){
    int ans = 0,flow;
    while(bfs()) while((flow=dfs(S))) ans += flow;
    return ans;
}

int n,p[MAXN],q[MAXN];
bool vis[MAXN];
int belp[MAXN],belq[MAXN];

inline void dfs(int v,int now,int p[],int bel[]){
    vis[v] = 1;bel[v] = now;
    if(vis[p[v]]) return;
    dfs(p[v],now,p,bel);
}

int main(){
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",p+i),++p[i];
    FOR(i,1,n) scanf("%d",q+i),++q[i];
    FOR(i,1,n) if(!vis[i]) ++N,dfs(i,N,p,belp);
    FOR(i,1,n) vis[i] = 0;
    FOR(i,1,n) if(!vis[i]) ++N,dfs(i,N,q,belq);
    S = N+1;T = N+2;N = T;
    int ans = n;
    FOR(i,1,n){
        if(p[i] == q[i]){
            if(p[i] == i){
                ans--;continue;
            }
            else{
                add(belp[i],belq[i],1);
                add(belq[i],belp[i],1);
            }
        }
        else{
            if(p[i] == i && q[i] != i){
                add(belq[i],T,1);
            }
            else if(p[i] != i && q[i] == i){
                add(S,belp[i],1);
            }
            else{
                add(belq[i],belp[i],1);
            }
        }
    }
    printf("%d\n",ans-Dinic());
    return 0;
}
/*
p: 割左边=不转 右边=转
q反过来 
何时答案会-1:
p[i]=q[i]=i 无论如何都会-1
p[i],q[i] != i 同时不转
p[i]=i,q[i]!=i 2不转
p[i]!=i,q[i]=i 1不转
p[i]=q[i],p[i],q[i]!=i  同时转
*/

AGC038 部分题解

E

题意

题解

F

题意

题解

One comment

Leave a Comment Cancel reply

I'm back

NOI2021 退役记

SDOI2020 退役记

点双连通分量 & 圆方树学习笔记

CSP2019 游记

此内容被密码保护

Stoer Wagner 算法

CF 1404 题解

树上启发式合并学习笔记

CF1398 题解

AGC038 部分题解

E

题意

题解

F

题意

题解