2024牛客多校1
2024年第一场多校赛，打的很一般，多校之前vp的几场多校成绩还不错，一场比赛直接打回原形。
赛时队友做的签到题C、H，吃了两发罚时，我自己推的A，出的很快，可惜没注意取模，吃了发罚时，长个记性吧。
A
给定n，m，p，问长度为n，并且都由小于 \(2 ^ m\) 的数组成，存在一个子序列的按位且等于1的序列有多少种。
假设n个数中，有k个数为奇数，那么对于其他 \(n - k\) 个偶数，他们的高 \(m - 1\) 位就可以随便选了。对于这k个奇数，要保证每一位这k个数中至少有一个是0。最后答案就为
\[\sum_{k = 1} ^ n C(k, n)(2 ^ {k - 1}) ^ {m - 1}2 ^ {(n - k)(m - 1)} \]其中每项依次代表，挑选k个奇数，奇数的每一位至少有1个0的方案数，有m-1位，偶数除最低位，其他任选的方案数
B
B题是A题的hard版本，将A中的至少一个子序列改为至少两个子序列
那么一个很直观的方法就是求出只存在一个子序列的方案数有多少种，在用A中的减去即可
首先是两个结论：
1、如果一个子序列按位且等于1，那么再添上任意一个奇数，那么得到的新序列按位且还等于1。
2、如果一个序列按位且等于1，且他没有按位且等于1的子序列，那么这个序列中每个数都有一位是0，且序列中其他数该位都是1。
我们第二个结论中该数的0位成为特殊位，那么我们就要保证每一个数都至少有1个特殊位。考虑使用do求一个奇数序列每个数都有关键位的方案数。 \(f[i][j]\) 代表j个数i个特殊位的情况。那么在不考虑吧这j个数的顺序的情况，转移方程为
\[f[i][j] = f[i - 1][j - 1] + j * f[i - 1][j] \]我们可以新填一个数，并给这个数一个新的特殊位，也可以把这个特殊位，分给原有的j个数其中之一。
有了j个数i个特殊位的方案数之后我们还需要做些什么呢？顺序问题！因为这j个数每个数都有属于自己独特的特殊位，所以他们必然两两不同，那么他们放入序列中的顺序问题，直接去乘全排列就好。还有什么呢？对于这j个数，他们只是拥有i个特殊位，这i个特殊位还需要从m-1位中挑选出来。这i个特殊位，拥有他们的数这一位是0，其他数全是1，那么其他m-1-i位需要放什么呢？首先肯定不能全1，如果全1这些奇数按位且就不等于1了。其次这些数也不能只有一个1，如果只有一个1，这些数的特殊位就会变多，会和特殊位更多的情况干扰。所以每一位的方案数就是 \(2^k-1-k\) 。再枚举一些奇数的个数这题就结束了，好了上一下代码吧。代码只供参考
void solve() {
for (int i = 2; i <= n; i++) { // 枚举奇数个数
i64 t = qpow(2ll, i);
i64 res = qpow((t - 1 + p) % p, m - 1);
i64 k = ((t - 1 - i ) % p + p) % p;
for (int j = 1; j <= m - 1; j++) {
pw[j] = pw[j - 1] * k % p; // 求非特殊位的方案数
}
for (int j = i; j <= m - 1; j++) { // 枚举特殊位个数
res -= c[m - 1][j] * f[j][i] % p * fac[i] % p * pw[m - 1 - j] % p;
res = (res % p + p) % p;
}
res = res * c[n][i] % p * qpow(2ll, (n - i) * (m - 1) % p) % p;
ans = (ans + res) % p;
}
}