「DTOI-5」进行一个排的重 (Min Ver.) 题解

· · 题解

本题需要使用分类讨论。

这道题我们需要分 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;
}