自动搬运

查看原文

来自洛谷，原作者为

	FFTotoro 龙猫

搬运于2025-08-24 22:47:12，当前版本为作者最后更新于2023-05-02 08:52:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本题需要使用分类讨论。

这道题我们需要分 $2$ 种情况讨论：

1. 当重排前存在 $i$ 满足 $p_i=q_i=n$：

   重排后要使得答案最小，则必须把满足 $a_i=(p_i,q_i)=(n,n)$ 的元素放在排列的第一项，让后面的数都没有贡献，所以第一问的答案是 $2$；

   把 $(n,n)$ 固定在开头后，后面 $n-1$ 个元素可以任意排列，第二问的方案数共有 $(n-1)!$ 种。

2. 当重排前不存在 $i$ 满足 $p_i=q_i=n$：

   重排后要使得答案最小，则必须把 $p_i=n$ 的一项或 $q_j=n$ 的一项放在排列的第一项；

   不妨设把 $p_i=n$ 放在第一项，$q_j$ 必然会比它前头的数大，只有排列第一项产生 $2$ 的贡献和 $q_j$ 产生的至少为 $1$ 的贡献，第一问答案是 $3$；

   如果我们把 $p_i=n$ 放在第一项，那么考虑 $q_j$ 怎么放才能产生正好为 $1$ 的贡献：只要不把大于 $q_i$ 的数放在 $q_j$ 的前面即可（因为如果我们这么做，那么会再产生若干贡献），方案数即为 $\dfrac{(n-1)!}{n-q_i}$。对称地，考虑把 $q_j=n$ 放在第一项的情况，总方案数即为 $\dfrac{(n-1)!}{n-q_i}+\dfrac{(n-1)!}{n-p_j}$。

除法可以用乘法逆元实现。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
const int mod=998244353;
int f(int n){
  int s=1;
  for(int i=2;i<=n;i++)
    (s*=i)%=mod;
  return s;
}
int qpow(int a,int b){
  int r=1;
  while(b){
    if(b&1)r=r%mod*a%mod;
    a=a%mod*a%mod; b>>=1;
  }
  return r;
}
int inv(int x){return qpow(x,mod-2);}
// 快速幂求逆元
main(){
  ios::sync_with_stdio(false);
  int n,x,y; cin>>n;
  vector<pii> a(n);
  for(auto &i:a)cin>>i.first;
  for(auto &i:a)cin>>i.second;
  for(auto [p,q]:a){
    if(p==n)x=q; if(q==n)y=p;
  } // 找到 q[i] 和 p[j]
  if(x==n)cout<<"2 "<<f(n-1)<<endl; // 第一种情况
  else cout<<"3 "<<f(n-1)*((inv(n-x)+inv(n-y))%mod)%mod<<endl; // 第二种情况
  return 0;
}