P7567

· · 个人记录

「MCOI-05」魔仙

构造题的难度一般都会被评成这个样子。。。讲实话这种题放在比较久远的高联二试我觉得完全不为过。。。也可能这个世界只有我不会做构造题。。。谔谔。。。不过真正体会到什么叫构造题总会有群魔乱舞的现象。。。

这个题直接去想构造的难度非常大，因为你不知道有解的数到底有什么特点，一个平凡的数拿来构造是很费事的，所以先要设法找到有解的充要条件。

尝试构造几个较小的数：1，2，3 显然无解；4 的解法样例已经给出了；5，7 也是显然无解，6 需要稍微想一下，会发现它也无解；但是 8 可以拆为 -2，-4，1，1，1，1，1，1。

我们虽然只试了少数几个数，但现在完全可以凭借数学直觉，大胆猜想只有在 n\equiv 0\pmod 4 的时候有解，因为这里感觉到：乘积就是用前面两个数凑出来的，而后面的 1 或 -1 就是用来满足 \sum a_i=0 这个条件的；当 n 是偶数时尚不太好像，但 n 是 4 的倍数时就感觉非常可做。

于是我们可以开始尝试证明，有解的充要条件是 n\equiv 0 \pmod 4。（虽然已经可以开始做了。这里的证明我只能说非常难想，感觉没有特别简明易懂的方法。除非可能数学直觉非常敏锐的人可以一眼看出。）

  1. 如果说 \{a_n\} 这个数列中没有偶数，那么奇数个奇数之和为奇数，与 \sum a_i=0 矛盾。

  2. 如果说 \{a_n\} 这个数列中只有 1 个偶数，那么 \prod a_i=n 为偶数，即 n-1 是奇数，奇数个奇数之和为奇数，奇数加上偶数为奇数，故 \sum a_i 为奇数，与 \sum a_i=0 矛盾。

  3. 如果说 \{a_n\} 这个数列中有 2 个偶数，那么 n-2 是偶数，偶数个奇数之和是偶数，偶数加偶数还是偶数，与条件不矛盾。此时 \prod a_i=n 必为 4 的倍数。

于是乎，着手构造。

设 n=4k。

我们先尝试构造 1\times 4k 和 4\times k，发现都没有太好的性质。

那么就构造 2\times 2k，正好又都是两个偶数。

这个时候我们想方法拿 1 去凑解。

可以想到待定系数：

2\times 2k \times 1^t\times(-1)^{4k-2-t}

列个方程，解出来 t=k-2 时是对的。

但后来发现，这个正负性我们还想没有考虑。

那么我们还需要讨论 k 的奇偶。

不过有了上面的方法，这里的讨论就显得简明很多了。

  1. 若 k 是偶数，则上面的构造就已经够用了。

  2. 若 k 是奇数，容易想到让 2\times 2k 变成 2\times (-2k)（直觉），然后同样待定系数，解得 t=3k-2。

然后输出就好了。

代码：

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;

ll T,n,k;

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

void writeln(ll x) {
    write(x);putchar('\n');
}

int main() {

    T=read();

    while(T--) {
        n=read();
        if(n%4==0) {
            k=n/4;
            if(k&1) {
                write(2);putchar(' ');write(-2*k);
                for(ll i=1;i<=3*k-2;i++) {
                    putchar(' ');write(1);
                }
                for(ll i=1;i<=k;i++) {
                    putchar(' ');write(-1);
                }
            }
            else {
                write(-2);putchar(' ');write(-2*k);
                for(ll i=1;i<=3*k;i++) {
                    putchar(' ');write(1);
                }
                for(ll i=1;i<=k-2;i++) {
                    putchar(' ');write(-1);
                }
            }
        }
        else {
            printf("w33zAKIOI");
        }
        putchar('\n');
    }

    return 0;
}