ARC163C 典中典之猪猪吃答辩与裂项模型

· · 个人记录

书接上回。

有一个模型叫做猪猪吃答辩，就是说猪猪在吃饭的时候啊，会把答辩切碎然后搅匀再吃，所以我们这次依然可以考虑这件事情。

我们先把答辩拆开：

\begin{aligned}1&=1-\frac{1}{2}+\frac{1}{2}-\frac{1}{3}+\frac{1}{3}-\cdots -\frac{1}{n}+\frac{1}{n}\\&=\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\cdots+\frac{1}{n(n-1)}+\frac{1}{n}\end{aligned}

这样构造大多数情况下都是正确的，除了 n=t(t+1),t\in \mathbb{Z} 的情况。此时我们发现 \frac{1}{n}=\frac{1}{t(t+1)}，那么这个 \frac{1}{n} 会出现两次。

于是我们考虑拼起来：由于 2\mid t(t+1)，那么把两个 \frac{1}{n} 加在一起，在结尾将 \frac{1}{n(n-1)} 拆成 \frac{1}{3n(n-1)} 加 \frac{2}{3n(n-1)} 即可。例如 n=2\cdot 3=6，按照原本构造应为 \frac{1}{2}+\frac{1}{6}+\frac{1}{12}+\frac{1}{20}+\frac{1}{30}+\frac{1}{6}，但是又因为 \frac{1}{6} 重复了，把两个 \frac{1}{6} 变成 \frac{1}{3}，再把 \frac{1}{30} 拆成 \frac{1}{90}+\frac{1}{45} 即可。

但这又有个问题，存在某个 n=t(t+1)，它是某个 k(k+1) 的两倍时，即使我们将两个 \frac{1}{n} 并了起来，\frac{2}{n} 依然是重复的分数。例如 n=12，\frac{2}{12}=\frac{1}{6}=\frac{1}{2\cdot 3}，你把 \frac{1}{12} 拼起来，\frac{1}{6} 又会重复。

智慧的猪猪打表发现 n\le 500 时这样的数只有 12 和 420，这两个数的方案是好构造的。特判即可。

void solve() {
    n = rd();
    int t = sqrt(n);
    if (t * (t + 1) == n) {
        if (n == 2) {
            puts("No");
            return;
        }
        puts("Yes");
        if (n == 12) {
            puts("2 4 12 20 30 42 56 72 90 110 396 198");
            return;
        }
        if (n == 420) {
            for (int i = n - 2; i; i--) {
                if (i == 5) continue;
                wr(i * i + i), pc(' ');
            }
            wr(28), pc(' '), wr(3 * n * (n - 1)), pc(' '), wr(3 * n * (n - 1) / 2), pc('\n');
            return;
        }
        for (int i = n - 2; i; i--) {
            if (i == t) continue;
            wr(i * (i + 1)), pc(' ');
        }
        wr(n / 2), pc(' '), wr(3 * n * (n - 1)), pc(' '), wr(3 * n * (n - 1) / 2), pc('\n');
        return;
    }
    puts("Yes");
    for (int i = 1; i <= n - 1; i++) {
        wr(i * (i + 1)), pc(' ');
    }
    wr(n), puts("");
}

signed main() {
    int T = rd();
    while (T--) solve();
    return 0;
}