【学习笔记】CF1713F Lost Array

应该可以看出来是做了$n$次异或前缀和。那么$a_i$对$b_j$的贡献相当于从$(1,i)$走到$(j,n)$的路径方案数$\left(\genfrac{}{}{0ex}{}{j+n-i-1}{j-1}\right)$，有贡献当且仅当$(n-i)\cap (j-1)=0$ 。将$a$序列反转就能得到$a_i$对$b_j$有贡献当且仅当$i\cap j=0$。

方便起见，我们让$n=2^k$，可以通过在$a$序列末尾补零实现。我们令$i=U-i(U=2^k-1)$，那么$b_i$就等于$a_i$的子集和。因为是异或所以做$FMT$的时候不需要考虑$-1$的系数，因此$a_i$也等于$b_i$的子集和。

然而对于$b_i$一段前缀的值我们是不知道的。这就比较麻烦了。

我们不妨将问题做一些泛化：

$1.1$ 有两个自然数$n$,$t$满足$n\le 2^t$（不满足$t$最小了）

$1.2$ 已知$a_n,a_{n+1,}...,a_{2^t-1}$（不限制为$0$了）以及$b_{2^t-n},b_{2^t-n+1},...,b_{2^t-1}$的值，并且满足$a_i$,$b_i$互为子集异或和，问是否存在合法解。

考虑到$a$,$b$两边剩下$n$,$2^t-n$个数不知道，一定存在一边$\le 2^{t-1}$。

如果我们能把其中一边全部解出来，那么另一边做一个子集和就能得到答案。

假设$n\le 2^{t-1}$。只需要消除$a$序列$[2^{t-1},2^t-1]$对$b$序列$[2^{t-1},2^t-1]$的贡献，然后解$a$序列$[0,2^{t-1}-1]$和$b$序列$[2^t,2^t-1]$这两个部分即可。因为此时$b$序列是$a$序列的子集和，所以$a$序列作逆变换还是可以得到$b$。$n>2^{t-1}$的情况类似。

复杂度$O(n\log n)$。

ps:求子集的异或和可以用下面这一段代码实现。

void conv(int *a,int *b,int m){
	int n=1<<m;for(int i=0;i<n;i++)b[i]=a[i];
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			if(j>>i&1)b[j]^=b[j^(1<<i)];
		}
	}
}
1
2
3
4
5
6
7
8

如果有bug记得联系博主。

#include
#define fi first
#define se second
#define ll long long
#define pb push_back
#define db double
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N=1e6+5;
int n,b[N],a[N],c[N],m;
void conv(int *a,int *b,int m){
	int n=1<<m;for(int i=0;i<n;i++)b[i]=a[i];
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			if(j>>i&1)b[j]^=b[j^(1<<i)];
		}
	}
}
void solve(int *a,int *b,int m,int n){
	if(n==(1<<m)){
		conv(b,a,m);
		return;
	}
	if(n==0){
		conv(a,b,m);
		return;
	}
	if(n<=(1<<m-1)){
		conv(a+(1<<m-1),c,m-1);
		for(int i=(1<<m)-n;i<(1<<m);i++){
			b[i]^=c[i-(1<<m-1)];
		}solve(a,b+(1<<m-1),m-1,n);
		conv(a,b,m);
	}
	else {
		conv(b+(1<<m-1),c,m-1);
		for(int i=n;i<(1<<m);i++){
			a[i]^=c[i-(1<<m-1)];
		}solve(a+(1<<m-1),b,m-1,n-(1<<m-1));
		conv(b,a,m);
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;int m=0;while((1<<m)<n)m++;
	for(int i=(1<<m)-1;i>=(1<<m)-n;i--)cin>>b[i];
	solve(a,b,m,n);for(int i=n-1;i>=0;i--)cout<<a[i]<<" ";
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49