比赛时在 Typora 上瞎推着式子结果就出来了(
先给出一个结论,满足条件的 \(N\) 一定至少有两个偶数因子,也就是 $N\mod 4=0 $。
证明:
设 \(N=\prod^n_{i=1}a_i\),则 \(\sum^n_{i=1}a_i=0\)。
令 \(N\) 为奇数,则它所有的因子也都是奇数,即 $a_1, a_2,\ldots,a_n $ 都是奇数,一共有 \(N\) 个数,所以数字的个数也是奇数,奇数个奇数之和是奇数,即 \(\sum^n_{i=1}a_i\) 为奇数,与 \(\sum^n_{i=1}a_i=0\) 矛盾,不成立。
令 \(N\) 只有一个偶数因子,不妨设这个偶数因子为 \(a_1\),移项,得:\(\sum^n_{i=2}a_i=-a_1\) ,\(N\) 为偶数,则 \(N-1\) 为奇数,奇数个奇数之和为奇数,即 \(\sum^n_{i=2}a_i\) 为奇数,与 \(\sum^n_{i=2}a_i=-a_1\) 矛盾,不成立。
所以 \(N\mod 4=0\)。
那么怎么说明当 \(N\mod 4=0\) 时一定有解呢?
构造出解就行了(逃
令 \(N=4k\),
若 \(k\) 为奇数,则 $2\times (-2k)\times 1^{3k-2}\times (-1)^k=N $,\(1+1+3k-2+k=N\),\(2-2k+3k-2-k=0\),满足条件。
若 \(k\) 为偶数,则 \((-2)\times (-2k)\times 1^{3k}\times (-1)^{k-2}=N\) ,\(1+1+3k+k-2=N\),\(-2-2k+3k-(k-2)=0\),满足条件。
代码:
#include<bits/stdc++.h>
using namespace std;
#define rg register
#define ll long long
#define inf 0x7f7f7f7f
#define mod 998244353
inline int read(){
rg int ret=0,f=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
while(isdigit(ch)){ret=ret*10+ch-48;ch=getchar();}
return f?-ret:ret;
}
int t,n;
int main(){
t=read();
while(t--){
n=read();
if(n%4) puts("w33zAKIOI"); //无解。
else{
int p=n/4;
if(p&1){ //根据 k 分类。
printf("%d %d ",2,-2*p);
for(rg int i=1;i<=3*p-2;++i) putchar('1'),putchar(' ');
for(rg int i=1;i<=p;++i) putchar('-'),putchar('1'),putchar(' ');
}else{
printf("%d %d ",-2,-2*p);
for(rg int i=1;i<=3*p;++i) putchar('1'),putchar(' ');
for(rg int i=1;i<=p-2;++i) putchar('-'),putchar('1'),putchar(' ');
}
putchar('\n');
}
}
return 0;
}
//My bones are titanium,but my heart is made of stars