AT_arc102_c
非常好的容斥题。
首先我们显然要枚举不能等于的点数 \(x\),然后发现两个筛子点数 \(\ne x\) 并不好做。
接下来的推导都是在我们确定 \(x\) 的情况下的。
考虑将限制转化为不存在任意筛子组合的 \((p, x - p)\),满足 \(1 \le p \le x - p \le k\),根据列出的不等式,容易发现整数对的个数为 \(y = \left \lfloor x / 2 \right \rfloor - \max(x - k, 1) + 1\) 个。
这题的妙处就在于它是对不满足条件的对数(相同的算作一对)容斥。也就是我们不在乎整数对内部具体地数值,只在乎他们的对数。这样做的好处是后面可以方便地计算他们的方案数。
然后计算至少 \(i\) 对的组合的方案数设为 \(g_i\),则显然从 \(y\) 种数对中选择 \(i\) 对的方案数为 \(\binom{y}{i}\),剩下有 \(n - 2i\) 个数,因为是容斥,有至少的限制,所以剩下的可以任意分配。考虑插空法,就是将 \(n - 2i\) 个无差别的筛子分为 \(k\) 组,每组可以空,于是方案数为 \(\binom{n - 2i + k - 1}{k - 1}\)。
我们得出 \(g_i = \binom{n - 2i + k - 1}{k - 1}\)。考虑其容斥系数为 \((-1)^i\),将 \(g_i\) 相加。我们就得出了对于每个 \(x\) 的答案。