D

神秘构造。

有一个关键观察是，col一列 \(n\) 次相当于翻转所有，于是就能从第 \(n\) 列开始，生产第 \(1\) 列，生产第 \(2\) 列，直到生产第 \(n-1\) 列，于是只剩下最后一列没有还原，考虑如何还原。

注意到在生产过程中无论是循环左移还是col一列 \(n\) 次，都没有改变每一行的异或和，或者一起改变一行的异或和，于是我们只需要调整每行的异或和即可。

我们大体的思路是使用最后一行和最后一列调整异或和，先将所有数变为 \(0\)，后将最后一列变为 \(1\)，然后从第 \(n-1\) 行开始逐行调整异或和，直到第 \(1\) 行，最后再调整 \((n,n)\) 的奇偶性。具体方法如下，代码中下标从 \(0\) 开始：

首先可以通过

for(int i = 0; i < n; i++) cnt += ve[n - 1][i] + ve[i][n - 1];
cnt -= ve[n - 1][n - 1];
while(cnt < n) {
    while(ve[n - 1][n - 1]) row(n - 1);
    col(n - 1), cnt++;
}

将最后一行最后一列中 \(1\) 的数量调整到多于 \(0\) 的数量，然后就可以

cnt = 0;
for(int i = 0; i < n; i++) cnt += ve[i][n - 1];
while(cnt) {
    if(ve[n - 1][n - 1]) cnt--;
    while(ve[n - 1][n - 1] == 0) row(n - 1);
    col(n - 1);
}

将最后一列变为 \(0\)，然后通过

for(int i = 0; i < n; i++) cnt += ve[n - 1][i];
while(cnt) {
    while(ve[n - 1][n - 1] == 0) row(n - 1);
    col(n - 1), cnt--;
}

将最后一行变为 \(0\)，通过col最后一列 \(n\) 次，可以将最后一列变为 \(1\)，然后就可以逐行调整异或和了

for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
        parity[i] ^= ve[i][j] ^ goal[i][j];
    }
}
for(int i = n - 2; i >= 0; i--) {
    if(!parity[i]) row(n - 1);
    col(n - 1);
}

最后再调整 \((n,n)\) 的奇偶性，这里的思路是先(col n, row n) \(n-1\) 次，把 \(A_1 ~ A_{n-1}\) 存到第 \(n\) 行的前 \(n-1\) 列，这个时候第n行就在第n列里了，可以直接用col操作调奇偶性，然后再操作回去即可，代码如下：

if(parity[n - 1]) { // 5n
    for(int i = 0; i < n - 1; i++) col(n - 1), row(n - 1);
    if(n % 2 == 0) col(n - 1);
    for(int i = 0; i < n - 1; i++) row(n - 1), col(n - 1);
    for(int i = 0; i < n; i++) col(n - 1);
}

这样奇偶性就调整好了，然后就能按照最开始的生产方式还原

for(int j = 0; j < n - 1; j++) { // 2n*(n-1) = 760
    vector<int> tmp;
    for(int i = 0; i < n; i++) {
        if(ve[i][n - 1] == goal[i][j]) row(i);
        else tmp.push_back(i);
    }
    for(int i = 0; i < n; i++) col(n - 1);
    for(int i : tmp) row(i);
}

总次数为 \(2n(n-1)+\Omicron(n)\)。

J

考虑什么情况下区间集会产生多于 \(1\) 种可能排列，若现在从小到大考虑到了 \(x\)，有 \(2\) 种情况：

在 \(1\sim x\) 的数中，至少有 \(2\) 个数在所有 \(m_i \leq x\) 的区间的并之外，那么这 \(2\) 个数是可以互换位置的，不合法、
考虑 \(m_i < x\) 的区间的并，不满足第一种情况的先排除，于是最多只有 \(1\) 个数 \(y\) 在这个区间的并之外。由于第一种情况的限制，\(x\) 必须被覆盖，即在 \(m_i=x\) 的区间的交中，那么 \(y\) 不能被 \(m_i=x\) 的区间的交覆盖，否则 \(x,y\) 可交换，不合法。

有了这 \(2\) 条限制之后我们毛估估一下发现就可以唯一确定一个排列了，考虑如何计数。令 \(f(x,p)\) 表示考虑到了 \(x\)，且 \(p\) 没有被覆盖的方案数，\(p=0\) 则所有 \(\leq x\) 的数都被覆盖。

考虑两类数 \(a,b\)，其中 \(a\) 与 \(x\) 之间所有数 \(\leq x\)，\(b\) 与 \(x\) 之间有一个数 \(> x\)，那么有转移

\(f(x-1,0)\to f(x,0)\)，要求 \(x\) 被覆盖
\(f(x-1,0)\to f(x,x)\)，要求 \(x\) 不被覆盖
\(f(x-1,a)\to f(x,a)\)，要求 \(x\) 被覆盖，且 \(a\) 不被覆盖
\(f(x-1,a)\to f(x,0)\)，要求 \(x,a\) 被覆盖，且所有新加入的区间的交不包含 \(a\)
\(f(x-1,b)\to f(x,b)\)，要求 \(x\) 被覆盖

由于排列随机，故 \(\#a\approx\Omicron(n\ln n)\)，可以暴力转移。

vector<Z> f(n + 1, 0);
Z mul = 1;
f[0] = 1;
for(int i = 1; i <= n; i++) {
    ll l = pos[i], x = pos[i], r = pos[i];
    while(p[l] <= p[x]) l--;
    while(p[r] <= p[x]) r++;
    ll t = (x - l) * (r - x);
    Z pt = qpow(2, t) - 1, ipt = 1 / pt;
    mul *= pt;
    vector<pair<int, Z>> add;
    add.push_back({p[x], f[0] * ipt});
    for(ll a = l + 1; a < r; a++) if(a != x) {
        ll u, v;
        if(a < x) {
            u = (x - a) * (r - x);
            v = (a - l) * (r - x);
        } else {
            u = (x - l) * (a - x);
            v = (x - l) * (r - a);
        }
        Z pu = qpow(2, u) - 1, pv = qpow(2, v) - 1;
        add.push_back({0, f[p[a]] * (pt - pu - pv) * ipt});
        add.push_back({p[a], -f[p[a]]});
        add.push_back({p[a], f[p[a]] * pu * ipt});
    }
    for(auto [a, b] : add) {
        f[a] += b;
    }
}
Z ans = accumulate(f.begin(), f.end(), Z(0)) * mul;

THC

2nd Ucup Semifinal Tutorial

D

J