题目链接
题目解法
很不错的题
首先题目保证了一定有解，所以不用考虑奇怪的无解情况
从列中的数字种类入手
如果一列中有数字 \(c\) 恰好只有第 \(x\) 行存在，那么第 \(x\) 行一定在答案序列中
考虑选了第 \(x\) 行会牵连一些行不能选，那么把这些行去掉，继续跑上面的操作
最后得到的序列一定是：对于每一列，出现过的数一定出现在恰好 \(2\) 行中
为什么？首先出现的数的种类是 行数\(/2\)，根据鸽巢原理，如果有一个数出现 \(>2\) 次，那么一定有至少一个数出现次数 \(=1\)
所以限制变成了这两行中只能选一行，不难想到建图，即在这两行之间连边，然后做二分图染色（保证合法）
因为每个联通块染了 \(1\) 个点之后整个块的颜色就固定了，所以方案数为 \(2^{联通块数}\)，构造就染色时取 \(color=1\) 的行就可以了
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
return FF*RR;
}
const int N=1100,P=998244353;
vector<int> G[N];
int n,a[N][N],col[N];
bool tag[N],cho[N];
void cover(int x){
tag[x]=true;
if(col[x]) cho[x]=true;
for(int y:G[x]) if(!tag[y]) col[y]=col[x]^1,cover(y);else assert(col[y]!=col[x]);
}
void clr(){
F(i,1,n<<1) cho[i]=tag[i]=false;
F(i,1,n<<1) G[i].clear();
}
void add_edge(int x,int y){ G[x].pb(y),G[y].pb(x);}
void del(int x){
F(i,1,n<<1){
if(tag[i]) continue;
F(j,1,n) if(a[x][j]==a[i][j]){ tag[i]=true;break;}
}
}
int sum[N],id[N],id2[N];
void work(){
n=read();
F(i,1,n<<1) F(j,1,n) a[i][j]=read();
while(true){
int x=-1;
F(j,1,n){
F(i,1,n) sum[i]=0;
F(i,1,n<<1) if(!tag[i]) sum[a[i][j]]++,id[a[i][j]]=i;
F(i,1,n) if(sum[i]==1){ x=id[i];break;}
if(x!=-1) break;
}
if(x==-1) break;
cho[x]=true,del(x);
}
F(j,1,n){
F(i,1,n) id[i]=id2[i]=-1;
F(i,1,n<<1) if(!tag[i]){
if(id[a[i][j]]==-1) id[a[i][j]]=i;
else assert(id2[a[i][j]]==-1),id2[a[i][j]]=i;
}
F(i,1,n) if(id[i]!=-1) assert(id2[i]!=-1),add_edge(id[i],id2[i]);
}
int cnt=1;
F(i,1,n<<1) if(!tag[i]) cnt=cnt*2%P,cover(i);
printf("%d\n",cnt);
F(i,1,n<<1) if(cho[i]) printf("%d ",i);puts("");
clr();
}
int main(){
int T=read();
while(T--) work();
return 0;
}