题解：P15362 [CTS 2026] 谜题 II

· · 题解

题意：

给定一张 2\times 2^k 的网格图，求其拓扑序个数对 2 取模。

观察与基本结构：

首先普通 DAG 难以直接计数，考虑把限制容斥掉一部分，此时我们希望得到一些树状结构。容斥一条边经典的就是没有边减去反向边，考虑我们使用这种操作来转化。

众所周知 \bmod 2 意义下组合数 \binom{n}{m_1,m_2,...m_k} 有值当且仅当 m_1,m_2,...m_k 二进制下无交（证明考虑用 lucas 定理归纳）。

考虑 \bmod 2 意义下的拓扑序计数带来了什么：发现若有多个连通块，它们之间分配系数是一个多重组合数，只可能在每个联通块大小二进制无交时有值，而和为 2 的幂次的多个正整数显然不可能满足，所以联通块个数不为 1 一定没有贡献。然后对于树的拓扑序，考虑 F_u=\binom{sz_{u}-1}{sz_{v_1},sz_{v_2},..,sz_{v_k}}\prod F_{v_i}，根据上述结论要求子树大小二进制无交。

基本形态一：对于割边没有这条边时没有贡献，模 2 减和加没有区别，所以割边可以随意反向。

基本形态二：对于形如 a_1>a_2,a_2>a_3,a_3>a_4,a_1>a_4 的限制，显然可以删去 a_1>a_4。

基本形态三：成环一定无解，所以容斥后出现环的情况可以直接忽略。

上手容斥：

我们容易计算拓扑序的形态是一棵固定方向（根向或叶向）的树。以下我们尝试把这张图中所有的横向边向右指，每个点有且仅有一条出边，此时构成一棵根向树。

我们尝试一个一个 2\times 2 的方格去做，然后对于横向边因为要么删去要么向右所以直接考虑，纵向边对于每个方格只考虑左侧的，对于右侧的在下一个方格考虑。

使用上述三种基本形态加上基本的容斥思想可以完成特殊性质 B。整理后结论为：若 a_i\neq b_{i+1} 则存在一种左侧边上指下，上方边删去的转移。若 c_i=b_{i+1} 则存在一种左侧边下指上，下方边删去的转移。然后发现一列两个点只有一个有从左侧来的子树，记 dp_{i,0/1} 表示到了第 i 列，之前的全都连在了第 i 列上面的点还是下面的点即可转移。

对于相邻两列纵向边方向相同的情况，考虑将左侧边变为删去加反向，删去后本方格横向边均为割边，可以直接指向右，反向即为特殊性质 B 的转移。此时记录上下两个从左侧接来的子树大小即可，因为有贡献的情况左边的点一定全部能联通到右边，所以只要记上方点接的子树大小即可。直接转移可以做到 O(T4^k)。

优化：

考虑什么情况下一列上下两个点接的子树大小都不为 0，一定是相邻两列纵向边方向相同之后两条边都向右，上下个子树大小均加一，这种操作不会改变上下子树大小差值。然后对于其他转移，因为会把上下作为同一个点的两个子树，所以要求上下子树大小二进制无交，这样的转移复杂度等价枚举子集复杂度，然后可以根据上下差找到上一次合并的位置进行转移。所以只要记录 dp_{i,0/1} 表示到了第 i 列，之前的全都连在了第 i 列上面的点还是下面的点即可转移。

此时复杂度是 O(T3^k)，还不够优。我们考虑题目给出的交互格式奇怪的把所有测试数据一次给出，dp 状态与题目边的方向限制都只有零和一。所以我们可以尝试压位转移，直接压会有点问题的是两子树大小一路加一的转移要求 b_i 相同，只要在扫描的同时将每组数据 b_i 连续段前的值清空即可。复杂度变为 O(3^k+T2^k)，可以通过。

代码：

//#include "puzzle.h" 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef pair<int,int> pii;
#define fi first
#define se second
typedef double db;
#define pb push_back
#define eb emplace_back
#define bcnt __builtin_popcount
const int inf=1e9+7;
const int N=6e5+5;
const int mod=998244353;
//const int mod=1e9+7;
int n,m,t,pre[35][N];
uint a[N],b[N],c[N],dp[N][2],S;
char s[N];
uint sol(){
    dp[1][0]=S;
    for(int o=0;o<t;o++){
        pre[o][1]=1;uint x=(1u<<o);
        for(int i=1;i<m;i++) pre[o][i+1]=((b[i+1]&x)==(b[i]&x)?pre[o][i]:i+1);
    }
//  for(int o=0;o<t;o++){
//      puts("pre:");
//      for(int i=1;i<=m;i++) printf("%d ",pre[o][i]);
//      puts("");
//  }
    for(int i=1;i<m;i++){
        int s=i*2-1;
        uint lim=(b[i+1]^a[i]);
        for(int j=s;j;j=((j-1)&s)){
            int x=j-1,y=(s^j);
            if(x>=y){
                int p=((x-y)>>1)+1;
                dp[i+1][1]^=(dp[p][0]&lim);
            }else{
                int p=((y-x)>>1)+1;
                dp[i+1][1]^=(dp[p][1]&lim);
            }
        }   
        lim=(S^(b[i+1]^c[i]));
        for(int j=s;j;j=((j-1)&s)){
            int y=j-1,x=(s^j);
            if(x>=y){
                int p=((x-y)>>1)+1;
                dp[i+1][0]^=(dp[p][0]&lim);
            }else{
                int p=((y-x)>>1)+1;
                dp[i+1][0]^=(dp[p][1]&lim);
            }
        }   
        for(int o=0;o<t;o++){
            uint x=(1u<<o);x^=S;
            for(int j=pre[o][i];j<pre[o][i+1];j++) dp[j][0]&=x,dp[j][1]&=x; 
        }
    } 
    //for(int i=1;i<=m;i++) printf("xy:%d %d\n",dp[i][0],dp[i][1]);
    uint ans=0;
    for(int i=m;i;i--){
        for(int o=0;o<2;o++){
            for(int j=0;j<t;j++){
                int x=(m-i)+(o^1)*(i*2-2)+((b[m]>>j)&1),y=(m*2-1-x);
                if(!(x&y)) ans^=(dp[i][o]&(1u<<j));
            }
        }
    }
    //printf("ans:%d\n",ans);
    for(int i=1;i<=m;i++) dp[i][0]=dp[i][1]=0;
    return ans;
}
unsigned puzzle(int T,int k,vector<unsigned> A,vector<unsigned> B,vector<unsigned> C){
    unsigned int ans=0;
    n=k,m=(1<<k),t=T;
    for(int j=0;j<t;j++) S|=(1u<<j);
    //printf("S:%u\n",S);
    for(int j=0;j<m-1;j++) a[j+1]=A[j];
    for(int j=0;j<m;j++) b[j+1]=B[j];
    for(int j=0;j<m-1;j++) c[j+1]=C[j];
    ans=sol();
    return ans;
}