CF Gym 上的原题保证序列长度为 \(2\) 的幂,这里介绍的做法可以针对 \(n\) 任意(虽然也没强到哪儿去)
首先充要条件是序列中所有数之和是 \(\lfloor\dfrac{n}{2}\rfloor\) 的倍数,因为每次操作对序列中所有数之和的增量都是 \(\lfloor\dfrac{n}{2}\rfloor\) 的倍数。而最终序列中所有数都是 \(0\),是 \(\lfloor\dfrac{n}{2}\rfloor\) 的倍数。
考虑判定有无解之后怎么处理。我们考虑设 \(n\) 次操作选择的 \(x\) 分别是 \(x_1,x_2,x_3,\cdots,x_n\),那么我们如果确定了每次选择的下标,那么求解 \(x_i\) 的过程相当于解一个由 \(n\) 个方程 \(n\) 个未知数组成的方程组。根据线性代数的知识,如果咱不考虑 \(x_i\) 必须是整数这个限制,那么只要左边的矩阵是满秩的,就必然存在恰好一组合法的 \(\{x_i\}\)。又因为每一次操作必须恰好选择 \(\lfloor\dfrac{n}{2}\rfloor\) 个下标,因此左边系数矩阵中每一列。因此问题转化为我们需要找到一个 \(01\) 矩阵,满足这个矩阵中每一列恰好有 \(\lfloor\dfrac{n}{2}\rfloor\) 个 \(1\) 且矩阵满秩。
对 \(n\) 分奇偶:
- 如果 \(n\) 是奇数,那么构造 \(a_{(i+j)\bmod n+1,i}=1\),其中 \(i\in[1,n],j\in[0,\lfloor\dfrac{n}{2}\rfloor)\)。
- 如果 \(n\) 是偶数,那么构造如下:
- \(a_{1,i}=1,i\in[1,n-1]\)。
- \(a_{(i+j)\bmod(n-1)+2,i},i\in[1,n-1],j\in[1,\dfrac{n}{2}-1]\)。
- \(a_{i,n}=1,i\in[2,\dfrac{n}{2}+1]\)。
容易证明构造出的矩阵的满秩的。
当然构造出矩阵之后还要进行高斯消元,并且 \(n^3\) 高斯消元肯定是行不通的,但是由于我们构造出的矩阵的特殊性,可以手动高斯消元:
- 对于 \(n\) 是奇数的情况,直接先将 \(n\) 个式子相加求出 \(\sum x_i\),然后拿 \(\sum x_i\) 减掉剩余的部分求得单个 \(x_i\)。
- 对于 \(n\) 是偶数的情况,以 \(x_n\) 为主元,将 \(x_1,x_2,\cdots,x_{n-1}\) 都表示成 \(kx_n+b\) 的形式然后带会第一个式子解出 \(x_n\)。
至于 \(x_i\) 必须是整数的限制,你手玩 \(n\) 比较小的情况就会发现,由于我们的有解性保证了 \(\sum a_i\) 是 \(\dfrac{n}{2}\) 的倍数,因此你解出来的 \(x_n\) 也是整数,因此我们的构造是合法的。
const int MAXN=2048;
int n,a[MAXN+5],sum;ll A[MAXN+5][MAXN+5],B[MAXN+5];
vector<pii>G[MAXN+5];ll d[MAXN+5];
void dfs(int x,int f){
for(pii pp:G[x]){
int y=pp.fi,z=pp.se;if(y==f)continue;
d[y]=d[x]+z;dfs(y,x);
}
}
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
// freopen("magic.in","r",stdin);
// freopen("magic.out","w",stdout);
scanf("%d",&n);n=1<<n;
for(int i=1;i<=n;i++)scanf("%d",&a[i]),sum+=a[i];
if(sum%(n+1>>1))return puts("NO"),0;
int m=n+1>>1;
if(n%2){
puts("YES");printf("%d\n",n);
for(int i=1;i<=n;i++)A[n+1][i]=a[i];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)A[i][(i+j-2)%n+1]=1;
int cur=0;
for(int j=1;j<=n;j++)if(A[i][j])++cur,A[n+1][j]-=2*cur;
}
// for(int i=1;i<=n+1;i++)for(int j=1;j<=n;j++)printf("%d%c",A[i][j]," \n"[j==n]);
ll s=0;for(int i=1;i<=n;i++)s+=A[n+1][i];s/=m;
for(int i=1;i<=n;i++){
printf("%lld ",A[n+1][i]+A[n+1][(i+m-2)%n+1]-s);
for(int j=1;j<=n;j++)if(A[i][j])printf("%d ",j-1);
printf("\n");
}
}else{
puts("YES");printf("%d\n",n);
for(int i=1;i<=n;i++)A[n+1][i]=a[i];
for(int i=1;i<n;i++){
A[i][1]=1;
for(int j=1;j<m;j++)A[i][(i+j-2)%(n-1)+2]=1;
int cur=0;
for(int j=1;j<=n;j++)if(A[i][j])++cur,A[n+1][j]-=2*cur;
}
for(int i=2;i<=m+1;i++)A[n][i]=1;
int cur=0;
for(int j=1;j<=n;j++)if(A[n][j])++cur,A[n+1][j]-=2*cur;
// for(int i=1;i<=n+1;i++)for(int j=1;j<=n;j++)printf("%d%c",A[i][j]," \n"[j==n]);
for(int i=2;i<n;i++)if(A[n][i]==A[n][i+1]){
int p=0,q=0;
for(int j=1;j<n;j++){
if(A[j][i]&&!A[j][i+1])p=j;
if(!A[j][i]&&A[j][i+1])q=j;
}
//b_q-b_p=A_{n+1,i+1}-A_{n+1,i}
G[p].pb(mp(q,A[n+1][i+1]-A[n+1][i]));
G[q].pb(mp(p,A[n+1][i]-A[n+1][i+1]));
}dfs(1,0);
ll V1=A[n+1][1],V2=A[n+1][n/2+2];
for(int i=1;i<n;i++)if(i!=(n/2)+1)V1-=d[i];
for(int i=1;i<n;i++)if(i!=(n/2)+1&&A[i][n/2+2])V2-=d[i];
assert((V1-V2)%(n/2)==0);
B[1]=(V1-V2)/(n/2);B[n/2+1]=V1-1ll*(n-2)*B[1];
for(int i=1;i<n;i++)if(i!=(n/2)+1)B[i]=d[i]+B[1];
B[n]=A[n+1][2];
for(int i=1;i<n;i++)if(A[i][2])B[n]-=B[i];
for(int i=1;i<=n;i++){
printf("%d ",B[i]+2);
for(int j=1;j<=n;j++)if(A[i][j])printf("%d ",j-1);
printf("\n");
}
}
return 0;
}
/*
5
1 3 5 7 11
*/
/*
10
1 7 2 5 4 9 6 3 10 8
*/