CF1296F - Harry The Potter
题目大意
给定 \(n\) 个数 \(a_i\) （ \(a_i\) 可以 \(<0\) ) 和两种操作
1.对于任意 \(a_i\) 和任意 \(x\) ， \(a_i\rightarrow a_i\pm x\)
2.对于任意 \(a_i,a_j\) 和 \(x\) , \(a_i\rightarrow a_i-x,a_j\rightarrow
a_j-x-1\)
用最少操作将 \(a_i\) 都变成0
分析
考虑最基本的策略：
1.选择两个数 \(a_i,a_j\)
，将其中较大 \(a_i\) 的减去 \(a_j\pm 1\) ，同时删掉 \(a_j\)
2.最后剩下的就通过操作1解决
我们希望能能尽量多地通过操作1对于某一组数的子集进行匹配，
使得对于这个子集内的数操作的最后一次能使得 \(a_i,a_j\) 一起消失
那么现在问题分为两步
1. 判定一个子集合法
对于一个集合S,(|S|>1)，考虑对于它进行匹配
模拟每次选择两个进行操作的过程可以发现，实际上只需要操作到最终总和为0
而不断操作的过程中，实际上会修改每个 \(S_i\) 对于总和的贡献系数（最终是 \(\pm 1\) ）
同时，每次操作产生 \(\pm 1\)
的常数，并且最终的常数可以是任意一个能通过 \(|S|-1\) 个 \(\pm
1\) 生成的数
（因为可以通过调整操作使得合法）
那么可以给出判定集合匹配的条件
1.那么将这个集合分裂为两个集合 \(S_1,S_2\) 并且 \(S_1,S_2\ne \empty\) ，使得 \(|Sum_1-Sum_2|\) 能够通过 \(|S|-1\) 个 \(\pm
1\) 合成
即 \(|Sum_1-Sum_2|<|S|\) ，且
\(|Sum_1-Sum_2|\equiv |S|-1 \pmod
2\)
奇偶性对于加减法始终保持不变，可以直接判定
如果暴力枚举判定 \(S_1,S_2\)
，复杂度为 \(O(3^n)\approx 34e8\)
但是实际上有很多剪枝，比如如果有一个子集能完成匹配，自己就不用再匹配
然而也有稳定算法（。。。）
因为实际上要求的是 \(-|S|< Sum_1-Sum2
<|S|\) 的形式，可以 \(\text{Meet in
the middle}\) +双指针解决
复杂度为 \(O(\sum \binom{n}{i}
2^{\frac{i}{2}} i)\) ，实际上由于常数不满这里几乎不用时间
稍微算一下复杂度级别，大概是 \(\sum n
\binom{n-1}{i-1} \sqrt 2^{i}=\sqrt 2n(\sqrt 2+1)^{n-1}\)
（实际上也并不小？）
2. 求解最优匹配
最终我们要将全集分解为若干子集以及散部，最大化子集个数
暴力枚举复杂度依然为 \(O(3^n)\)
，卡卡就能过（还很快
但是想用集卷积试试
设表示合法匹配集的多项式为 \(G(x)\)
则 \([x^S]G(x)=\left\{\begin{aligned} 1
&& \text{S is a match}\\-\infty &&
\text{otherwise}\end{aligned} \right.\)
定义 \(\max\) 子集卷积 \([x^S]F\times G(x)=\max\{ [x^T]F(x)+[x^{S\Delta
T}]G(x)\}\)
实际上我们求的的是 \(F(x)=\text{exp}{(G(x))}\) 的最大项
众所周知一次普通子集卷积/子集 \(\text{exp}\) 是 \(O(n^22^n)\)
的（如果用集合幂+形式幂exp的做法，常数可能会更小）
而取 \(\max\) 操作难以放入多项式做
\(\text{FMT}\) 以及乘法
额外增加 \(dp\)
值的维度会使得复杂度爆炸
但是鉴于 \(dp\)
值很小，可以在值域内压位，将加法转化为乘法
判断压位的每一位是否有出现即可，每次卷完只保留最大的一位
因为实际上匹配最多 \(\frac{n}{2}\)
个，需要压10位
因为多项式实际上很空，每位在卷积过程中出现的次数并不多
所以压位压位长度不需要太长 （虽然我long long
以内压不进去）
还是比较可以实现的，因此这一部分复杂度为 \(O(2^nn^2)\)
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
| typedef __uint128_t ull;
const int N=25,M=1<<20,INF=1e9+10;
const ull D=1000;
int n,m;
ll A[N],S[M];
int c[M],chk[M];
ull F[21][M],G[21][M];
ll X[1<<10],Y[1<<10];
int C;
ll B[N];
ll Fix(ll x,ll y){
return floor((long double)x/y);
}
int Norm(ull &x){
ull T=1,c=0;
while(T*D<=x) T*=D,c++;
return x=T,c;
}
void FMT(ull *F){
for(int i=1;i<=m;i<<=1) {
for(int l=0;l<=m;l+=i*2) {
for(int j=l;j<l+i;++j) {
F[j+i]+=F[j];
}
}
}
}
void IFMT(ull *F){
for(int i=1;i<=m;i<<=1) {
for(int l=0;l<=m;l+=i*2) {
for(int j=l;j<l+i;++j) {
F[j+i]-=F[j];
}
}
}
}
int main() {
rep(i,1,rd()) {
ll x=rd<ll>();
if(x) A[n++]=x;
}
if(!n) return puts("0"),0;
m=(1<<n)-1;
rep(i,1,m) {
c[i]=c[i&(i-1)]+1,S[i]=S[i&(i-1)]+A[__lg(i&-i)];
rep(j,0,n-1) if(i&(1<<j)) chk[i]|=chk[i^(1<<j)];
if(chk[i]) { chk[i]=2; continue; }
if(c[i]<2 || (S[i]&1)==(c[i]&1)) continue;
ll l=Fix(S[i]-c[i]+2,2),r=Fix(S[i]+c[i]-1,2);
C=X[0]=Y[0]=0;
rep(j,0,n-1) if(i&(1<<j)) B[C++]=A[j];
int k=C/2;
int l1=(1<<k)-1,l2=(1<<(C-k))-1;
rep(j,1,l1) X[j]=X[j&(j-1)]+B[__lg(j&-j)];
rep(j,1,l2) Y[j]=Y[j&(j-1)]+B[__lg(j&-j)+k];
rep(j,1,l2) if(X[0]+Y[j]>=l && X[0]+Y[j]<=r){ chk[i]=1; break; }
rep(j,1,l1) if(X[j]+Y[0]>=l && X[j]+Y[0]<=r){ chk[i]=1; break; }
rep(j,0,l2-1) if(X[l1]+Y[j]>=l && X[l1]+Y[j]<=r){ chk[i]=1; break; }
rep(j,0,l1-1) if(X[j]+Y[l2]>=l && X[j]+Y[l2]<=r){ chk[i]=1; break; }
if(chk[i] || l1<=1 || l2<=1) continue;
sort(X+1,X+l1),sort(Y+1,Y+l2);
int p=l2-1;
rep(j,1,l1-1) {
while(p>0 && X[j]+Y[p]>r) p--;
if(p>0 && X[j]+Y[p]>=l) { chk[i]=1; break; }
}
}
rep(i,1,m) if(chk[i]==1) G[c[i]][i]=D;
int ans=0;
F[0][0]=1;
rep(i,2,n) FMT(G[i]);
rep(i,0,n) {
if(i) IFMT(F[i]);
rep(j,(1<<i)-1,m-(1<<(n-i))+1) if(F[i][j]) {
if(c[j]!=i) F[i][j]=0;
else cmax(ans,Norm(F[i][j]));
}
if(i+2<=n) {
FMT(F[i]);
rep(S,0,m) if(F[i][S]) rep(j,2,n-i) F[i+j][S]+=F[i][S]*G[j][S];
}
}
printf("%d\n",n-ans);
}
|