划分题解

题目大意

现有集合 $A=\{0,1,\dots,n\}$，函数 $f_m(S)$ 表示从 $S$ 中选出两个不同的数相加等于 $m$ 的方案数（选出的数无序）。

现在要给出一种构造，构造出集合 $S$，另一部分即为 $T$（全集是 $A$），使得 $\forall 1\leq m\leq n$，$f_m(S)=f_m(T)$ 。

不需要你输出 $S$ 所有元素，你只需要以下列方式输出：

1. 令 $1\in S$
2. 设 $x=(\prod\limits_{r\in S} r)\bmod 998244353$
3. 输出 $x$

题目采用 $\text{SPJ}$ 评测。

Solution

首先一眼发现这个 $\text{SPJ}$ 是假的，因为很难通过若干个数的乘积（模 $998244353$ 的情况下）来还原出唯一的 $S$。结合出题人比较懒的特点， 应该是不会真的把所有可能都列出在 $\text{SPJ}$ 里面的。所以答案是唯一的。

但是我没看出来。

当然可以证明，但是我不会， 现在会了：

证明：考虑我们 $0\sim n-1$ 的情况都处理好了，现在放 $n$。因为 $0\in T$，所以如果放在 $T$ 里 $f_n(T)$ 就会增加 $1$；如果放在 $S$ 里 $f_n(S)$ 不变 。所以不存在 $n$ 既可以放在 $S$ 又可以放在 $T$ 的情况。

这道题的做法有很多，推导过程也很有趣，类似于大力打表找规律、手玩样例找规律，但是因为我推导最后假了，所以我不觉得有趣。

直接上结论吧：元素 $i\in S$ 当且仅当 $\text{popcount}(i)$ 为奇数。

原因：令 $x,y\in S$，$x+y=n$，$x\neq y$。在二进制下从低到高找到第一个不同的位（显然可以做到），对 $x,y$ 把那一位翻转得到 $x’$ 和 $y’$，显然加和仍然相等且二者互不相等，就可以给 $f_n(T)$ 做贡献。

现在怎么区分哪些元素到底怎么放不会混淆呢？发现 $x$ 与 $x’$ 的差别、$y$ 与 $y’$ 的差别就是 $\text{popcount}$ 的奇偶性发生了变化。所以我们可以规定一个集合内的 $\text{popcount}$ 奇偶性相同。

为什么上面写的是“原因”而不是“证明”？

因为我感觉作为证明就怪怪的，但是它正好自洽。果然信息竞赛不是数学竞赛。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int P=998244353,N=2e3+10;

int n,ans;

int popcount(int x)
{
    int cnt=0;
    for(int i=63;~i;i--)
        cnt+=((x>>i)&1);
    return cnt;
}

signed main()
{
    ans=1;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        if(popcount(i)&1)
            ans=ans*i%P;
    }
    printf("%lld\n",ans);
    return 0;
}