首页 > 其他分享 >[ARC140D] One to One

[ARC140D] One to One

时间:2024-08-01 15:11:10浏览次数:12  
标签:pii fr int num ans ARC140D define

神奇计数题。

先将所有确定的边连起来,一个比较关键的点是,将每个方案的贡献摊到每一个环上,即统计每个可能的环的方案数。设 \(a_i=-1\) 的数量为 \(num\)。

对于基环树来说,不论其他点怎么选这个环都存在,贡献为 \(n^{num}\)。

对于若干树构成的环来说,这种环有 $(t-1)!\prod \limits_{i=1}^t sz_i $ 个,对于每一个环,贡献为 \(n^{num-t}\)。

将树的贡献放到 dp 里面即可。

#include<bits/stdc++.h>
using namespace std;
#define N 2005
#define fr first
#define se second
#define p 998244353
#define ll long long
#define pii pair<int,int>
ll ans,fac[N],mi[N],f[N][N];
int n,m,num,a[N],vis[N];
basic_string<int> G[N];
pii dfs(int u){
    vis[u]=1;pii ans={1,G[u].size()};
    for(int v:G[u])if(!vis[v]){
        pii x=dfs(v);
        ans.fr+=x.fr;ans.se+=x.se;
    }return ans;
}
int main(){
    scanf("%d",&n);
    fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%p;
    mi[0]=1;for(int i=1;i<=n;i++)mi[i]=mi[i-1]*n%p;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[i]==-1)++num;
        else G[i]+=a[i],G[a[i]]+=i;//printf("%d %d\n",a[i],i);
    }
    for(int i=1;i<=n;i++)if(!vis[i]){
        pii x=dfs(i);
        if(x.fr==x.se/2)ans+=mi[num]%p;
        else a[++m]=x.fr;
    }
    f[0][0]=1;
    for(int i=1;i<=m;i++){
        f[i][0]=1;
        for(int j=1;j<=m;j++)
            f[i][j]=(f[i-1][j]+f[i-1][j-1]*a[i])%p;
    }
    for(int i=1;i<=m;i++)
        ans=(ans+f[m][i]*fac[i-1]%p*mi[m-i]%p)%p;
    printf("%lld",ans);
}

标签:pii,fr,int,num,ans,ARC140D,define
From: https://www.cnblogs.com/xcyyyyyy/p/18336690

相关文章

  • Atcoder ARC140D One to One
    考虑到对于\(n\)个点的连通块,那就有\(n\)条边,就是个基环树。如果这里面有\(1\)个\(-1\),那么就是\(n-1\)条边,就是一棵树。如果有\(2\)个\(-1\),\(n-2\)条边一定不连通,不可能出现。令\(-1\)的个数为\(c\)。那么先对于已知的边连上,如果一个连通块是基环树就直......
  • ARC140D 做题笔记
    洛谷题目链接ATcoder题目链接好题。(不过绝大部分题解全在瞎说)看到$n$个点$n$条边且每个点只有一条出边很容易的想到基环树。而最后每个连通块一定是一个基环树,那么统计连通块的数量就相当于统计基环树的数量。既然有基环树,这种题绝对不能枚举然后求连通块数量,一定是枚举......
  • [ARC140D] One to One
    首先有一个性质,每个点只有一条出边的图,每个联通块只能是基环树。那么有\(-1\)的连通块就一定是树。本题要求的是每种连边方案的联通块数量之和,把贡献拆开来算就可以转化......
  • 「ARC140D」One to One - 题解
    题解若对每一块进行考虑,那么对于一个有\(n\)个点\(n\)条边的块,也就是基环树或环来说,里面一定不会存在\(a_i=-1\)。否则就是一棵树了,那么也最多只会有一个\(a_i=-1\)......