Permutation Counting 4——The 2024 ICPC Asia East Continent Online Contest (I)

题意描述

给定n个范围（即每个位置可以选择的数据），问存在多少种方案构造出 1-n 的全排列

思路

首先我们考虑最暴力的方法，枚举所有的排列 p 依次检验这个排列是否满足题意。

为了检验这个 p 是否满足题意，我们可以构造出一个矩阵 $A$ 帮助我们检验。

例如我们给出一组数据

3

1 3

1 1

3 3

我们构造出的矩阵就应该是

$$ A=\left\{ \begin{matrix} \textcolor{red}{1} & 1 & 1 \\ 1 & 0 & \textcolor{red}{0} \\ 0 & \textcolor{red}{0} & 1 \end{matrix} \right\} $$

若 p 表示 1 3 2 我们可以根据$\prod ^{n}_{i=1}A_{i}p_{i}$是否为1得到 p 是否满足题意。这个排列显然是不满足的，对整体答案的贡献就是0。

而我们我们要求的总答案就是

$$ \sum _{p}\prod ^{n}_{i=1}A_{i}p_{i} $$

此时我们注意到

$$ \det \left( A\right) =\sum _{p}sgn\left( p\right) \prod ^{n}_{i=1}Aip_{i} $$

其中 $sgn(p)$ 表示 p 排列的逆序对数，根据逆序对数的奇偶有+1、-1两种取值。

而题目要求我们最重要要对2进行取模，所以奇偶性是一致的（请考虑在一个加法式子中，随意更改某些＋为-，该式子的奇偶性是否一致）。

问题就转化成了在模2的条件下，A矩阵的行列式是否为0。

$$ \begin{matrix} 1 & 1 & 1 & 1\\ 1 & 1 & 0 & 0\\ 0 & 0 & 1 & 1 \end{matrix} $$

比如这个矩阵我们一眼就能看出来是线性相关的，第一行+第二行便能得到第三行（在模2的情况下），似乎可以用线性基来解决，但是看一眼数据范围，1e6*1e6，包T的。我们考虑来使用区间这个性质。

直接计算是否线性相关这个问题是很难解决的，我们继续更换思路来解决这个问题。如果一个矩阵行列式为0，说明某个行向量能被其他行向量表达出来。

也就是说，如果我们有以下形式的矩阵。

$$ \begin{matrix} 1 & 1 & 1 & 1\\ 1 & 1 & 0 & 0\\ \end{matrix} $$

那么下面这个行向量

$$ \begin{matrix} 0 & 0 & 1 & 1 \end{matrix} $$

一定是不能加进来的。

我们从1-n遍历每个数的范围，并查看他能否被表示出来并进行处理。例如我们已经加入了三个范围。

$$ \begin{matrix} 0 & 0 & 1 & 1 & 1 & 1\\ 1 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & 0 & 0 \end{matrix} $$

如果添加的是 [1,4]（也就是 1 1 1 1 0 0 ），那他肯定就是能被表示出来的，因为第二个和第三个能表示出来[1,4]。

我们可以意识到能表示出来的数一定是某些个首部或者尾部都在相同位置或者首尾相连的数字表示出来的，我们认为这些首部或者尾部都在相同位置或者首尾相连的区间是一类的，他们能形成的新区间就是同一类的数字的区间相互叠加形成的。

我们可以通过处理找出来每一个点作为起点能属于哪个类，那同一个类里面所有的起点构成的区间都是能得到的。

例如上面这个矩阵的第一二三行，我们标记了一个类，第1，3，5，7列都是一个类里面的，那么[1,2],[1,6]等都是可以表示出来的。

现在给定一个区间[l,r]我们就需要判断 l 和 r+1 是否为同一个类，如果是，那输出0就结束了，若果不是那我们就需要合并两边的区间。

代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
struct DSU {//板子来源wida，懒得写了
    vector<int> fa, p, e, f;
    DSU(int n) {
        fa.resize(n + 1);
        iota(fa.begin(), fa.end(), 0);
        p.resize(n + 1, 1);
        e.resize(n + 1);
        f.resize(n + 1);
    }
    int get(int x) {
        while (x != fa[x]) {
            x = fa[x] = fa[fa[x]];
        }
        return x;
    }
    bool merge(int x, int y) { // 设x是y的祖先
        if (x == y) f[get(x)] = 1;
        x = get(x), y = get(y);
        e[x]++;
        if (x == y) return false;
        if (x < y) swap(x, y); // 将编号小的合并到大的上
        fa[y] = x;
        f[x] |= f[y], p[x] += p[y], e[x] += e[y];
        return true;
    }
 };
void solve(){
    int n;cin>>n;
    DSU dsu(n+1);
    vector<pair<int,int>> q(n);
    for(auto& [x,y]:q)cin>>x>>y;
    for(auto [x,y]:q){
        if(!dsu.merge(x,y+1)){
            return void(cout<<0<<'\n');
        }

    }
    cout<<1<<'\n';
}
signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t=1;
    cin>>t;
    while(t--) solve();
    return 0;
}

参考链接

行列式的妙用-ICPC2024Online1-C | ShwBlog (shwst.one)

The 2024 ICPC Asia East Continent Online Contest (I) 部分题解 - 博客 - bulijiojiodibuliduo的博客 (qoj.ac)