题解：P9306 「DTOI-5」进行一个排的重 (Minimum Version)

zsjaaaxy · 2026-04-27 21:39:10 · 题解

前言

https://www.luogu.com.cn/ticket/KLBA654812

思路

观察样例后容易发现第一问的答案总为 2 或 3，具体的，若 p_{i} 与 q_{i} 的最大值在同一个 i 取到，则答案为 2，否则答案为 3。

考虑如何求第二问答案。不妨类似求第一问分讨，容易发现当 p_{i} 与 q_{i} 的最大值在同一个 i 取到时，第二问答案为 (n-1)!，推导是显然的：将最大值放到最前面其他乱排。

类似的，当 p_{i} 与 q_{i} 的最大值不在同一个 i 取到时，我们先选一个最大值放在最前面，然后算这种方案的贡献。不妨设放 p_{f}=n 在最前面，我们注意到接下来一定是一段比 q_{f} 小的，后面乱排。我们可以枚举第一个大于 q_{f} 的位置，这种方案的贡献为 A^{i-2}_{q_{f}-1} \times A^{n-i}_{n-i}。

由于需要求排列数，需要费马小定理求逆元，时间复杂度 O(n \log n)。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000000,mod=998244353;
int n,p[N],q[N],op,sum[N],f1,f2;
int qpow(int x,int p)
{
    if(p==0)
    {
        return 1;
    }
    if(p==1)
    {
        return x;
    }
    int res=qpow(x,p>>1);
    return res*res%mod*qpow(x,p%2)%mod;
}
int C(int x,int y)
{
    if(y<x)
    {
        return 0;
    }
    return sum[y]*qpow(sum[y-x]*sum[x]%mod,mod-2)%mod;
}
int A(int x,int y)
{
    if(y<x)
    {
        return 0;
    }
    return sum[y]*qpow(sum[y-x],mod-2)%mod;
}
signed main()
{ 
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>p[i];
        if(p[i]==n)
        {
            f1=i;
        }
    }
    for(int i=1;i<=n;i++)
    {
        cin>>q[i];
        if(q[i]==n)
        {
            f2=i;
        }
    }
    sum[0]=1;
    for(int i=1;i<=n;i++)
    {
        sum[i]=sum[i-1]*i;
        sum[i]%=mod;
    }
    if(f1==f2)
    {
        cout<<"2 "<<sum[n-1]<<"\n"; 
    }
    else
    {
        cout<<"3 ";
        int ans=0;
        for(int i=2;i<=n;i++)
        {
            ans+=A(i-2,q[f1]-1)*A(n-i,n-i);
            ans%=mod;
        }
        for(int i=2;i<=n;i++)
        {
            ans+=A(i-2,p[f2]-1)*A(n-i,n-i);
            ans%=mod;
        }
        cout<<ans;
    }
    return 0;
}