C0392 B 【1109 B组】预处理器题解

Creeper_l · 2023-11-22 16:36:20 · 个人记录

题意：求有多少个长度为 n 的数组 a 满足以下条件。

条件一：l_{i} \le a_{i} \le r_{i}。
条件二：a_{i} 模 2 等于 p_{i}。
条件三：s \le \sum a_{i} \le t。

求答案模 mod 的值，mod 不一定是一个质数。

数据范围：n \le 13。

又积累到一个新的 Trick：看到这种 2^{n} 能过的数据范围，又是计数，可以往容斥方面想。

显然，a_{i}=2\times x_{i}+p_{i}，那么将构造数组 a 转化为构造数组 x，这样可以消除条件二。

发现可以把条件三转化为 a_{i} \le t 的答案减去 a_{i} \le s-1 的答案，这样更好统计答案。然后考虑转化条件一，把上界 r_{i} 去掉，做容斥即可。具体来讲，设 S 为一个 n 位的二进制串，如果第 i 为 1，就需要满足 a_{i} \ge r_{i}+1，为 0 则需要满足 a_{i} \ge l_{i}。最后的答案就是 S 中 1 的数量为偶数时的答案减去 S 中 1 的数量为奇数时的答案（容斥）。

那对于每一个 S，怎么计算答案呢？首先可以将 a_{i} 的和的上界 tot 减去每一个 a_{i} 的下界，因为每一个 a_{i} 都至少有这么多。然后问题就转化成了有 n 个相同盒子和 tot 个相同球，每个盒子可以放任意个球（可以为零），有多少种本质不同的放法，显然插板法直接做即可。

注意：mod 不是质数，没有逆元，所以在算组合数的时候要先把分母算出来，然后和分子一一约分，最后将分子相乘即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 15;
int n,s,t,mod,a[MAXN][2],p[MAXN];
inline int solve(int x)
{
    int ans = 0;
    for(int i = 0;i < (1 << n);i++)
    {
        int tot = x,op = __builtin_popcount(i) & 1;
        for(int j = 1;j <= n;j++)
        {
            if((i >> j - 1) & 1) tot -= a[j][1] + 1,tot -= (p[j] ^ (a[j][1] + 1)) & 1;
            else tot -= a[j][0],tot -= (p[j] ^ a[j][0]) & 1;;

        }
        if(tot < 0) continue;
        tot = tot / 2,tot += n;
        int res = 1,vis[MAXN] = {},a[MAXN],p = 1;
        for(int j = 1;j <= n;j++) p = p * j;
        for(int j = 1;j <= n;j++) 
        {
            int val = tot - j + 1;
            int g = __gcd(val,p);
            val /= g,p /= g;
            a[j] = val;
        }
        for(int j = 1;j <= n;j++) res = (res * a[j]) % mod;
        ans = (ans + res * (1 - 2 * op) + mod) % mod;
    }
    return ans;
}
signed main()
{
    cin >> n >> s >> t >> mod;
    for(int i = 1;i <= n;i++) cin >> a[i][0] >> a[i][1] >> p[i];
    cout << (solve(t) - solve(s - 1) + mod) % mod; 
    return 0;
}

C0392 B 【1109 B组】预处理器 题解

C0392 B 【1109 B组】预处理器题解