自动搬运

查看原文

来自洛谷，原作者为

	yeshubo_qwq 我是 luxu。

搬运于2025-08-24 22:42:29，当前版本为作者最后更新于2022-11-24 12:56:33，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

A

先从 $28$ 个孩子中选 $14$ 个孩子，给他们自己房间的钥匙，满足有 $14$ 个孩子分到的是自己房间的钥匙的条件。

剩下的 $14$ 个孩子要求分到的不是自己房间的钥匙，这是一个显然的错排问题。

将两部分乘起来就可以得到最后的答案。

B

要把排列 $A$ 转化到 $B$，有两种方法：

• 不断重复操作 $1$（转移到其下一个排列。如果当前排列已经是最后一个排列，那么下一个排列就是第一个排列）。

• 不断重复操作 $2$（转移到其上一个排列。如果当前排列是第一个排列，那么上一个排列就是最后一个排列）。

取步骤数最小值即可。

如何快速求出步骤数？用给定全排列在所有全排列中的排名！

求排名就要用到康托展开（不会可以去看看 【模板】康托展开）。

Code

注意：本题中所有涉及到的运算都不能取模，所以第一问会爆 long long，可以用 __int128 或者高精度。

#include <bits/stdc++.h>
#define int __int128
using namespace std;
void write(int x){
	if (x>9) write(x/10);
	putchar(x%10+'0');
}
namespace A{
	int F[30],i;
	vector <int> fac;
	void go(){
		for (F[2]=1,i=3;i<=14;i++) F[i]=(i-1)*(F[i-1]+F[i-2]);
		for (fac.push_back(1),i=1;i<=28;i++) fac.push_back(fac.back()*i);
		write(fac[28]/(fac[14]*fac[14])*F[14]);
	}
}
namespace B{
    int c[20],fac[20];
	int lowbit(int x){
		return x & - x;
	}
	void add(int x,int v){
		while (x<=17) c[x]+=v,x+=lowbit(x);
	}
	int sum(int x){
		int res=0;
		while (x>0) res+=c[x],x-=lowbit(x);
		return res;
	}
	int Get(string a){
		int ans=0,i; fac[0]=1;
		for (i=1;i<=17;i++) fac[i]=fac[i-1]*i;
		for (i=1;i<=17;i++) add(a[i]-'a'+1-(a[i]>'m'),1);
		for (i=1;i<=17;i++) ans+=sum(a[i]-'a'-(a[i]>'m'))*fac[17-i],add(a[i]-'a'+1-(a[i]>'m'),-1);
		return ans;
	}
	void go(){
		int x=Get(" aejcldbhpiogfqnkr");
		int y=Get(" ncfjboqiealhkrpgd");
		write(min(y-x,fac[17]-y+x));
	}
}
signed main(){
	return (getchar()=='A'?A::go():B::go()),0;
}