P8788 [蓝桥杯 2022 国 A] 填空问题 题解

yeshubo_qwq · 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;
}