WC2019 全国模拟赛第二场 T1 题解

又只会写T1…

题目链接

题意简述

给你一个排列 $p_{1..n}$，$a_{1..n}$ 为任意的一个排列，定义 $b[a_i]=a[p_i]$，求总共有多少个不同的 $b_{1..n}$ 。

做法

首先，对 $(i,p_i)$ 连边，会得到若干个环。

环上旋转一下（$\forall i\text{ on the cycle : }i\rightarrow p_i$）得到的置换是本质相同的。节点个数相同的环互换一下是本质相同的。

先计算把 $n​$ 个节点分成若干个环的方案数：（用 $siz[i]​$ 表示第 $i​$ 个环的大小，$k​$ 表示环的个数，$sum[i]​$ 表示 $\sum\limits_{j=i}^ksiz[j]​$）

$$S_1=\prod\limits_{i=1}^kC_{sum[i]}^{siz[i]}$$

然后去掉节点个数相同的环互相交换：（用 $num[i]$ 表示节点个数为 $i$ 的环的个数）

$$S_2=\frac{S_1}{\prod\limits_{i=1}^nnum[i]!}$$

然后乘上每个环旋转（旋转造成的不同方案数即固定某个数后剩下的数的排列个数）：

$$S_3=S_2\times\prod\limits_{i=1}^k(siz[i]-1)!$$

$S_3$ 就是最终的答案了。

参考代码

noi.ac 上最短解（其实计算方式和我是一样的..）：

#include<bits/stdc++.h>
#define mn 1111111
using namespace std;
long long n,i=1,s=1,j,x,p=998244353,a[mn],f[mn],v[mn],t[mn];
int main()
{
    scanf("%lld",&n); f[0]=f[1]=1; for (;i<=n;i++) scanf("%lld",a+i);
    for (i=2;i<=n;i++) f[i]=f[p%i]*(p-p/i)%p,(s*=i)%=p;
    for (i=1;i<=n;i++)
        if (!v[i])
        {
            for (j=i,x=0;!v[j];x++,j=a[j]) v[j]=1;
            (s*=f[x]*f[++t[x]]%p)%=p;
        }
    printf("%lld",s);
}

我自己赛时的辣鸡写法：

#include <iostream>
#include <cstdio>
#include <cctype>

using namespace std;

int read()
{
    int out=0;
    char c;
    while (!isdigit(c=getchar()));
    for (;isdigit(c);c=getchar())
    {
        out=out*10+c-'0';
    }
    return out;
}

const int N=1000010;
const int M=998244353;

void dfs(int u);
int c(int a,int b);

int n,p[N],dfn[N],low[N],sta[N],dfncnt,top,siz[N],tot,num[N];
int x,y,jc[N],inv[N],ans=1,sum;
bool ins[N];

int main()
{
    int i;

    n=sum=read();

    for (i=1;i<=n;++i)
    {
        p[i]=read();
    }

    for (i=1;i<=n;++i)
    {
        if (dfn[i]==0)
        {
            dfs(i);
        }
    }

    jc[0]=jc[1]=inv[0]=inv[1]=1;
    for (i=2;i<=n;++i)
    {
        inv[i]=(1ll*M*M-1ll*(M/i)*inv[M%i])%M;
    }
    for (i=2;i<=n;++i)
    {
        jc[i]=(1ll*jc[i-1]*i)%M;
        inv[i]=(1ll*inv[i-1]*inv[i])%M;
    }

    for (i=1;i<=tot;++i)
    {
        ans=1ll*ans*c(sum,siz[i])%M;
        sum-=siz[i];
    }

    for (i=1;i<=n;++i)
    {
        ans=1ll*ans*inv[num[i]]%M;
    }

    for (i=1;i<=tot;++i)
    {
        ans=1ll*ans*jc[siz[i]-1]%M;
    }

    cout<<ans;

    return 0;
}

int c(int a,int b)
{
    if (a==b||b==0)
    {
        return 1;
    }
    return 1ll*(1ll*jc[a]*inv[b]%M)*inv[a-b]%M;
}

void dfs(int u)
{
    dfn[u]=low[u]=++dfncnt;
    sta[++top]=u;
    ins[u]=true;
    if (dfn[p[u]]==0)
    {
        dfs(p[u]);
        low[u]=min(low[u],low[p[u]]);
    }
    else if (ins[p[u]])
    {
        low[u]=min(low[u],dfn[p[u]]);
    }
    if (low[u]==dfn[u])
    {
        siz[++tot]=1;
        while (sta[top]!=u)
        {
            ++siz[tot];
            ins[sta[top--]]=false;
        }
        ins[sta[top--]]=false;
        ++num[siz[tot]];
    }
}

所以说不要看到环就 tarjan…