CSP-S模拟赛20241004

标签：20241004 钦定 元素 个数 模拟 可以 考虑 CSP dp

A

你考虑 可以把这个数组当中的每个数表示成另一种形式：\(a_i = k_i\times x+b\)(其中\(x\)是模数，\(b\)为余数)。

对于求两个数是否对于某个余数同余，显然你要判断他们两个的差，即\(a_i-a_j\)，那么我们用上面那种形式表示其实就是\(a_i-a_j = (k_i-k_j) \times x\),所以你要判断整个数组的话只需要对每两个数的差求一个\(gcd\),如果这个\(gcd\)是\(1\)，显然，他们所有数不能对一个数同余，故选择的模数直接用\(2\)就可以让模出来最少的余数种类---仅有\(2\)种，否则的话，就可以通过余某个数把他们变成同余的，故答案就是\(1\)。

Code

B

场切的第一个第二题哈哈哈哈，首先你考虑这个如果做数学的话没法推到出来一个大的综合式子(别问为什么，两个小时没做出来)。
我们考虑做\(dp\)计数，设定\(dp_{i,j}\)表示当前选到了第\(i\)个数，当前的和为\(j\)。
那么考虑转移，其实挺好整，你考虑如果这一个选\(1\)，那么他能从\(dp_{i-1,j-1}\)转移过来。
如果选了\(j\)这个和，那么你考虑其实\(j/2\)的也能选到，因为你可以把这个序列当中的所有数都除以\(2\)，所以也可以转移。

注意，建议你正着枚举，也就是:

\[dp_{i,j} = dp_{i-1,j-1}+dp_{i,j*2} \]

那么这个时候，你对于\(j\)的枚举顺序应该是从大到小的，因为你在计算\(j\)的时候会找到\(j*2\)对吧，所以在第二维计算的时候，他是具有依赖性的哈哈哈。
记得判断\(j*2\)的范围一定是 \(\le i\)的。

D

考虑容斥把问题转化。
设定\(f_i\)表示至少钦定了\(i\)个数的出现次数不大于\(1\)，\(g_i\)表示你恰好钦定了\(i\)个数的出现次数不大于\(1\)。
得到公式：

\[f_i = \sum_{i=0}^{n}C_{j}^{i} g_j \]

反演得到:

\[g_i = \sum_{i=0}^{n}(-1)^{j-i}C_{j}^{i}f_j \]

解释一下这里为什么有组合数奥，显然，一开始你钦定了\(i\)个数，对于你目前找到的这\(j\)个数，有\(C_{j}^{i}\)种选法。

但是，你\(f_i\)的表示还需要有一个\(C_{n}^{i}\)，这是为什么呢？因为你在求这个\(f_i\)时一开始点的选择有\(C_{n}^{i}\)种选法，当你钦定了这\(i\)个数的时候，你还有\(C_{j}^{i}\)种可以移动的方法，这样可以理解吧。

那么你发现，答案其实就是\(g_0\)，显然啊！

对于钦定的\(i\)个元素，可以分为两类：出现一次的和没有出现的。对于没有出现过的元素可以不考虑，对于只出现一次的元素，设其个数为\(j\)，可以考虑将其划分为若干集合，然后再与未钦定的元素进行搭配。将相互区分的\(n\)个元素划分为\(k\)个不互相区分的非空集合方案数为\(\displaystyle {k \brace n}\)，

标签：20241004,钦定,元素,个数,模拟,可以,考虑,CSP,dp
From： https://www.cnblogs.com/grz0306/p/18447309