排序

2023年7月1日更新
发现不懂数学的自己是真的不行。这道题实际上是一个对第一类斯特林数 - OI Wiki的简单应用。
答案就是
$$\sum (lens - loops) = \sum_0^{组数} ( lens -组数 \cdot Stirling(MissingBlock,组数) + baseWeight) \\ 其中\quad 可以分组的数量 = MissingBlock - 1$$
代码实现

/*
 * @Date: 2023-07-01 09:16:56
 * @LastEditors: scarletborder baishuibeef@gmail.com
 * @LastEditTime: 2023-07-01 12:28:01
 * @FilePath: \test26_jisuanke\exQ\QueueWeight3.c
 */
#include <malloc.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef unsigned long long LL;
const int M = 10007;
const LL MOD = 998244353;
int n, m;
LL f[2001][2001];

void stirling(int n, int m)
{
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            f[i][j] = (f[i - 1][j - 1] + (LL)(i - 1) * f[i - 1][j]) % MOD;
        }
    }
}
long long c(int n, int m)
{
    if (m < n - m) {
        m = n - m;
    }
    long long ans = 1;
    for (int i = m + 1; i <= n; i++) {
        ans *= i;
    }
    for (int i = 1; i <= n - m; i++) {
        ans /= i;
    }
    return ans;
}
int main()
{
    int SourceSize;
    scanf("%d", &SourceSize);

    int* array = (int*)malloc(sizeof(int) * (SourceSize + 1));
    for (int i = 1; i <= SourceSize; ++i) {
        scanf("%d", &array[i]);
    }

    bool* isVisited = (bool*)calloc((SourceSize + 1), sizeof(bool));
    bool* isMissing = (bool*)calloc((SourceSize + 1), sizeof(bool));
    LL MissingNumber = 0; // 归属于缺失块的数字总数
    int MissingBlock = 0; // 缺失块
    int loops = 0;

    for (int i = 1; i <= SourceSize; ++i) {
        if (!isVisited[i]) { // 不进入此处，正常数到这，发现已经被访问了。或者缺失数也到这但是他是在第一个数前面的，但是由于-1阻挡成不了环
            // 本应该在缺失数里的到这，那么他的祖先可能有个isVisited
            int j = i;
            while (!isVisited[j] && array[j] != -1) {
                isVisited[j] = 1;
                j = array[j];
            }
            if (array[j] == -1 || isMissing[j]) { // 因为是-1停下来的，或者某数的祖先是缺失数里的
                if (array[j] == -1 && isMissing[j] != true) { // 是-1停下来的并且这个-1过去没有访问过，缺失块+1
                    ++MissingBlock;
                }
                if (!isMissing[j]) { // 如果联通的是-1并且这个-1没有被访问过
                    isVisited[j] = 1; //-1 的标志没有被记为1
                    isMissing[j] = 1; // 同理，下面的循环也不会置-1元素为1
                    MissingNumber++;
                }
                //
                int jj = i;
                while (!isMissing[jj]) {
                    isMissing[jj] = 1;
                    jj = array[jj];
                    MissingNumber++;
                }
            } else {
                ++loops;
            }
        }
    }
    LL baseWeight = SourceSize - loops - MissingNumber;

    // 根据我写的doc，开calcmissing部分
    LL ans = 0;
    if (MissingBlock == 0) {
        printf("%u", baseWeight % MOD);
        return 0;
    }
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    stirling(MissingBlock,MissingBlock);
    for (int m = 1; m <= MissingBlock; ++m) {
        ans += (MissingNumber - (LL)m + baseWeight) * f[MissingBlock][m];
        ans %= MOD;
    }
    printf("%u", ans);
    return 0;
}

抽象化

在初步将带有缺失数字和被缺失数字影响的位置全部找到进行以下讨论
将目前的带有-1和正数的序列化为一个个独立的不同方块。一个或多个数化为1个方块的条件是联通集母亲一样。即mother[currentArray[j]] != -1 联通直到=-1
现在根据环的思想，我们想要得到的是
$\sum {lens} - \sum {loops}$

---

现在我们所要讨论的就是对于每个子问题中的lens和loops
我们容易知道，每个子问题lens都是相同的，即初始情况下的无序序列中元素的总数
而我们子问题的个数就是对序列性容器Array中每个空缺的-1填入数字 MissingCount! missingcount是-1的个数

---

其次我们要问的就是子问题下loops的数量总和，但是这里我们不需要讨论每个子问题下loops的数量再加起来，而是直接找到$\sum loops$
这个时候就用到了我们之前抽象的方块。
在-1中填入不同的数字$\to$将方块的头部与某个其他方块的根部相连成为一个新的方块
$$\sum loops =A^2_{N} \cdot \sum {((分开的方块的区间个数)\cdot (这种区间个数出现次数)) + baseWeight}\\ 分开的方块的区间个数 = interval_i + 1\\ 这种区间个数出现次数=一系列相同挡板出现次数=C^{interval_i}_{N-1}\\ interval_i \in [0,N-1]\quad ( N是初始方块的数量,baseWeight是在初始化时找到的不带-1的环数)$$

---

在求出上面的solve后，

例如
-1 -1
A B
AB $\quad$ A B
interval = 0, Nblock = 0 + 1 = 1, times = $C^0_1$ = 1, $loops_0$ = $A^2_2\cdot 1 \cdot 1$ = 1
interval = 1, Nblock = 2, times = $C^1_1$=1,$loops_1$ = $A^2_2 \cdot 2 \cdot 1$ = 2
$\therefore \sum loops = 3$
$\therefore solve = \sum len - \sum loops = 2 * (2!) - 3 = 1$
只有-1的方块是一样的吗？