题解 【P7567 「MCOI-05」魔仙】

比赛时在 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
上一篇:生成函数入门


下一篇:力扣 2006. 差的绝对值为 K 的数对数目