Description
听着自己美妙的曲子，小 Z 进入了梦乡。在梦中，小 Z 仿佛又回到了自己纵横考场的年代。在梦中，小 Z 参加了一场考试，这场考试一共有 n 道题，每道题的最终得分都是一个大于等于 0 的整数。然而醒来后，小 Z 忘记了自己每道题的得分。他只记得自己计算过 m 次一些题目的分数和，每道题都被计算过，并且只被计算过一次。除此之外他还记得其中 t 道题的满分分别是多少（一道题的得分不会超过满分）。现在小 Z 想知道他这场考试有多少种得分情况（至少有一道题的得分不同就算不同的情况），因为这个答案可能很大，你只需要输出答案对 1,000,000,007 取模后的结果即可。
第一行两个整数 n,m 表示题目个数与求和次数。
接下来 m 行，每行以一个整数 k 开头，表示小 Z 这次对 k 道题进行了求和。
然后 k 个整数 a1~ak，表示这次求和的都是哪些题。最后一个整数 c 表示求和后的结果。
一行一个整数 t，含义见题目描述。
t 行，每行两个整数 r,L，表示第 r 道题的满分是 L。
Output
一行一个整数表示答案模 1,000,000,007 的结果。
“`
5 2
2 1 2 5
3 3 4 5 7
1
3 4
“`
Sample Output
“`
180
“`
HINT
对于 30%的数据：n,c≤8。
对于另外 40%的数据：t=0。
对于 100%的数据：1≤n,m≤1,000,000，0≤c,L≤1,000,000，0≤t≤20。
Source
湖南集训
Solution
容斥
没有限制？
\[C_{n+m-1}^{m-1}\]有限制，但限制的数量很少？
容斥。
统计合法的比较难 考虑统计不合法的
让?? 表示没有满足第i个方程，这样没有满足限制?? ≤ ?，就变成了满足?? ≥ ? + 1，我们让?? = ?? + ? + 1，其中?? ≥ 0
把原方程中的?? 用?? 换掉，这样就去掉了这个限制。对于一个枚举的集合S，把涉及到的方程全部修改后，就可以直接求出对应的答案。（因为方程比较多，所以先全部乘起来，然后每次把有修改的方程的原答案除去再乘上新答案）
注意一定要预处理逆元，不然会TLE。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| #include <cstdio>
#include <algorithm>
#define PROB "Equation"
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int INF = 1000000007;
const int maxn = 2000005;
const LL P = 1000000007;
inline int getint() {
int r = 0; bool b = true; char c = getchar();
while ('0' > c || c > '9') {if (c == '-') b = false; c = getchar();}
while ('0' <= c && c <= '9') {r = r * 10 + (c - '0'); c = getchar();}
if (b) return r;
return -r;
}
int n, m, t, cnt[maxn], inv[maxn], sum[maxn], fa[maxn], a[maxn], b[maxn], vis[maxn], dst[50];
LL ans, ANS = 1ll, frac[maxn], frav[maxn];
inline LL ksm(LL a, LL b) {
LL ret = 1ll, tmp = a;
while (b) {
if (b & 1ll) ret = (ret * tmp) % P;
tmp = (tmp * tmp) % P;
b >>= 1ll;
}
return ret;
}
inline LL C(int n, int m) {return frac[n]*frav[m]%P*frav[n-m]%P;}
inline LL cal(int n, int m) {return C(n+m-1, m-1);}
inline LL calc(int s) {
LL ret = ANS;
int ccc = 0, bel, tot = 0;
for (int i = 0; i < t; ++i)
if (s & (1<<i)) {
sum[fa[a[i]]] -= b[i] + 1;
if (sum[fa[a[i]]] < 0) ret = 0ll;
if (vis[fa[a[i]]] != s) {
vis[fa[a[i]]] = s;
dst[tot++] = fa[a[i]];
}
ccc ^= 1;
}
if (ret)
for (int i = 0; i < tot; ++i)
ret = ret * inv[dst[i]] % P * cal(sum[dst[i]], cnt[dst[i]]) % P;
for (int i = 0; i < t; ++i)
if (s & (1<<i))
sum[fa[a[i]]] += b[i] + 1;
if (ccc) return -ret;
return ret;
}
int main() {
freopen(PROB".in", "r", stdin);
freopen(PROB".out", "w", stdout);
n = getint(); m = getint();
frac[0] = 1ll;
for (int i = 1; i <= 2000000; ++i) frac[i] = frac[i-1] * LL(i) % P;
frav[2000000] = ksm(frac[2000000], P-2ll);
for (int i = 1999999; i >= 0; --i) frav[i] = frav[i+1] * LL(i+1) % P;
for (int i = 1; i <= m; ++i) {
cnt[i] = getint();
for (int j = 0; j < cnt[i]; ++j) fa[getint()] = i;
sum[i] = getint();
ANS = (ANS * cal(sum[i], cnt[i])) % P;
}
ans = ANS;
t = getint();
for (int i = 0; i < t; ++i) {
a[i] = getint();
b[i] = getint();
inv[fa[a[i]]] = ksm(cal(sum[fa[a[i]]], cnt[fa[a[i]]]), P-2ll);
}
for (int i = 1; i < 1 << t; ++i)
ans = (P + calc(i) + ans) % P;
printf("%lld\n", ans);
fclose(stdin);
fclose(stdout);
return 0;
}
|