题意：求有多少个长度为 \(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;
}