P10360 [PA 2024] Desant 3

又是神秘模 2 计数题。

题意

有 \(n\) 个人，每个人有一个 01 数字，有 \(m\) 次操作，从 \(1\) 开始轮流执行每个操作，操作给出 \(a_i,b_i\)，表示说若当前第 \(a_i\) 个人持有数字 1 且第 \(b_i\) 个人持有数字 0 则交换两个人的位置。对 \(k=1\sim n\) 求出有多少种分配数字的方案使得 1 的个数恰好为 \(k\) 且最终 1 的位置形成一段连续区间。

\(n\le 35,m\le 1000\)

分析

直接爆搜，时间复杂度显然为 \(O(2^n)\)。

一看这题就不太能做，考虑爆搜加剪枝，初始全是空，每次搜索往里面加数。

设 \(x=a_i,y=b_i\)，01 序列为 \(s\)，当 \(s_x,s_y\) 都是空时，一共有四种方案。由于当 \(s_x=1,s_y=0\) 或 \(s_x=0,s_y=1\) 时最终状态都是 \(s_x=0,s_y=1\)。我们可以利用模 2 的性质让这两个对称的状态的方案数抵消掉，这样这两种状态就不用搜下去了。

当 \(s_x,s_y\) 有一个为空时，一共有两种方案。但是我们发现可以约束成一种方案：假设当 \(s_y=0\) 时，若 \(s_x=0\) 则 \(s_y\) 任取；若 \(s_x=1\) 则（交换后）\(s_y=1\) 且 \(s_x\) 任取。这个任取我们没必要非得搜出来，直接让它等于空即可。

当 \(s_x,s_y\) 都不为空时，直接模拟即可，一共有一种方案。

最终 \(m\) 次操作结束后可能会有若干个空位置，枚举一下连续区间的左右端点然后 check 一下即可。由于每次有两种状态可以搜时空位置数会减少 2，所以总复杂度 \(O((n^2+m)2^{\frac{n}{2}})\)。

点击查看代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<numeric>
#include<map>
#include<unordered_map>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<set>
#include<array>
#include<tuple>
#include<ctime>
#include<random>
#include<cassert>
#include<chrono>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define j0 jj0
#define j1 jj1
#define y0 yy0
#define y1 yy1
#define IOS ios::sync_with_stdio(false)
#define ITIE cin.tie(0)
#define OTIE cout.tie(0)
#define PY puts("Yes")
#define PN puts("No")
#define PW puts("-1")
#define P0 puts("0")
#define P__ puts("")
#define PU puts("--------------------")
#define mp make_pair
#define fi first
#define se second
#define gc getchar
#define pc putchar
#define pb emplace_back
#define un using namespace
#define il inline
#define all(x) x.begin(),x.end()
#define mem(x,y) memset(x,y,sizeof x)
#define popc __builtin_popcountll
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
#define per(a,b,c) for(int a=(b);a>=(c);--a)
#define reprange(a,b,c,d) for(int a=(b);a<=(c);a+=(d))
#define perrange(a,b,c,d) for(int a=(b);a>=(c);a-=(d))
#define graph(i,j,k,l) for(int i=k[j];i;i=l[i].nxt)
#define lowbit(x) ((x)&-(x))
#define lson(x) ((x)<<1)
#define rson(x) ((x)<<1|1)
//#define double long double
//#define int long long
//#define int __int128
using namespace std;
using namespace __gnu_pbds;
using i64=long long;
using u64=unsigned long long;
using pii=pair<int,int>;
template<typename T1,typename T2>inline bool ckmx(T1 &qwqx,T2 qwqy){return qwqx>=qwqy?0:(qwqx=qwqy,1);}
template<typename T1,typename T2>inline bool ckmn(T1 &qwqx,T2 qwqy){return qwqx<=qwqy?0:(qwqx=qwqy,1);}
inline auto rd(){int qwqx=0,qwqf=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')qwqf=-1;ch=getchar();}while(ch>='0'&&ch<='9'){qwqx=(qwqx<<1)+(qwqx<<3)+ch-48;ch=getchar();}return qwqx*qwqf;
}
template<typename T>inline void write(T qwqx,char ch='\n'){if(qwqx<0){qwqx=-qwqx;putchar('-');}int qwqy=0;static char qwqz[40];while(qwqx||!qwqy){qwqz[qwqy++]=qwqx%10+48;qwqx/=10;}while(qwqy--){putchar(qwqz[qwqy]);}if(ch)putchar(ch);
}
bool Mbg;
const int mod=998244353;
template<typename T1,typename T2>inline void adder(T1 &x,T2 y){x+=y,x=x>=mod?x-mod:x;}
template<typename T1,typename T2>inline void suber(T1 &x,T2 y){x-=y,x=x<0?x+mod:x;}
const int maxn=40,maxm=1e3+5,inf=0x3f3f3f3f;
const long long llinf=0x3f3f3f3f3f3f3f3f;
int n,m,o[maxm][2];
int a[maxn],ans[maxn];
void dfs(int step){if(step==m+1){int fst=n+1,lst=0;rep(i,1,n)if(a[i]==1){fst=i;break;}per(i,n,1)if(a[i]==1){lst=i;break;}rep(l,1,fst){rep(r,l,n){if(a[r]==0)break;if(r>=lst)ans[r-l+1]^=1;}}return;}int x=o[step][0],y=o[step][1];if(a[x]==-1&&a[y]==-1){a[x]=a[y]=0,dfs(step+1),a[x]=a[y]=-1;a[x]=a[y]=1,dfs(step+1),a[x]=a[y]=-1;}else if(a[x]==-1||a[y]==-1){if(a[x]==0||a[y]==1)return dfs(step+1);swap(a[x],a[y]),dfs(step+1),swap(a[x],a[y]);}else{if(a[x]==1&&a[y]==0)swap(a[x],a[y]),dfs(step+1),swap(a[x],a[y]);else dfs(step+1);}
}
inline void solve_the_problem(){n=rd(),m=rd();rep(i,1,m)rep(j,0,1)o[i][j]=rd(); mem(a,-1),dfs(1);rep(i,1,n)write(ans[i],32);
}
bool Med;
signed main(){
//	freopen(".in","r",stdin);freopen(".out","w",stdout);fprintf(stderr,"%.3lfMB\n",(&Mbg-&Med)/1048576.0);int _=1;while(_--)solve_the_problem();
}
/**/