2022蓝桥杯国A

次林梦叶的小屋 / 2023-05-09 / 原文

《A填空问题》

数学前提：错排问题

结论：设C(n)为有n个人都错排了的方案数

C（n）= (n-1)(C(n-1)+C(n-2))

阶乘结论：n! 当n>20时会爆long long

数学前提：康拓展开 cantor

是用来求全排列中某一个排列在整个全排列的位数（即这个排列在全排列中是第几小）

具体：资料1 ，资料2

结论：∑sum(ai)* (n-i)!

　　　sum（ai）是比ai小的有多少个元素（除去已经固定的，不能再用的）

函数：reverse(str.begin(),str.end()) 常用来反转字符串

#include <iostream>
#include <algorithm>
#include <cstring>
#include <assert.h>
using namespace std;
typedef long long ll;
ll C[20];
ll q1()
{
    C[1] = 0, C[2] = 1;
    for (int i = 3; i <= 14; i++)
        C[i] = (ll)(i - 1) * (C[i - 1] + C[i - 2]);
    ll t = 1;
    for (ll i = 28, j = 2; i >= 15; i--)
    {
        while (j <= 14 && t % j == 0)
        {
            t /= j;
            j++;
        }
        t *= i;
    }
    return t * C[14];
}
ll fac[20];
//用来求这个排列是在全排列中的第几小
ll cantor(string a)
{
    ll na = 0;
    for (int i = 0; i < a.length(); i++)
    {
        ll sum = 0;
        for (int j = i; j < a.length(); j++)
            if (a[i] > a[j])
                sum++;
        na += sum * fac[17 - i - 1];
    }
    // 因为前面有na个比这个排列小，则这个排列排在第na+1位
    na++;
    return na;
}
ll q2()
{
    string a = "aejcldbhpiogfqnkr";
    string b = "ncfjboqiealhkrpgd";
    string c = "abcdefghijklnopqr";
    reverse(c.begin(), c.end());
    fac[1] = 1;
    for (ll i = 2; i <= 17; i++)
        fac[i] = fac[i - 1] * i;
    ll na = 0, nb = 0, nc = 0;
    na = cantor(a), nb = cantor(b), nc = cantor(c);
    ll ans = min(nc - nb + na, nb - na);
    return ans;
}
int main()
{

    string ans[] = {
        "1286583532342313400",
        "106148357572143",
    };
    char T;
    cin >> T;
    cout << ans[T - 'A'] << endl;
    return 0;
}