题意：听着自己美妙的曲子，小Z进入了梦乡。在梦中，小Z仿佛又回到了自己纵横考场的年代。在梦中，小Z参加了一场考试，这场考试一共有 n 道题,每道题的最终得分都是一个大于等于 0 的整数。然而醒来后，小Z忘记了自己每道题的得分。他只记得自己计算过 m 次一些题目的分数和，每道题都被计算过，并且只被计算过一次。除此之外他还记得其中 t 道题的满分分别是多少（一道题的得分不会超过满分）。现在小 Z 想知道他这场考试有多少种得分情况（至少有一道题的得分不同就算不同的情况），因为这个答案可能很大，你只需要输出答案对 109+7 取模后的结果即可。 输入格式：第一行两个整数 n,m 表示题目个数与求和次数。 接下来 m 行，每行以一个整数 k 开头，表示小Z这次对 k 道题进行了求和。然后 k 个整数 a1…ak ，表示这次求和的都是哪些题。最后一个整数 c 表示求和后的结果。 接下来一行一个整数 t，含义见题目描述。 接下来 t 行，每行两个整数 r,L，表示第 r 道题的满分是 L。 感觉和之前的一题几乎一样：http://blog.csdn.net/mintgreentz/article/details/72772688，直接容斥一发就过了
#include<bits/stdc++.h> typedef long long ll; const int N = 1e6 + 50; const int P = 1e9 + 7; const int INF = 1e9; int n, m, k[N], c[N], L[N], l[N], a, first[N], s; ll fac[N*2], inv[N*2]; template <typename T> void read (T &x) { x = 0; char c = getchar(); for (; !isdigit(c); c = getchar()); for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; } struct rec{ int y, next; }mp[N]; void ins(int x, int y) { mp[++s] = (rec) {y, first[x]}; first[x] = s; } ll pwr(ll x, int k) { ll ans = 1; for (; k; k >>= 1, x = x * x % P) if (k & 1) ans = ans * x % P; return ans; } void init() { fac[0] = inv[0] = 1; for (int i=1; i < N*2; i++) fac[i] = fac[i - 1] * i % P; inv[N*2 - 1] = pwr(fac[N*2 - 1], P - 2); for (int i=N*2 - 2; i > 0; i--) inv[i] = inv[i + 1] * (i + 1) % P; } int calc(int x) { int ret = 0; for (; x; x >>= 1) ret += x & 1; return ret; } ll C(ll n, int k) { if (n < k) return 0; return fac[n] * inv[k] % P * inv[n - k] % P; } int main() { init(); read(n);read(m); for (int i=1; i <= m; i++) { read(k[i]); for (int j=1; j <= k[i]; j++) { read(a); ins(i, a); } read(c[i]); } for (int i=1; i <= n; i++) L[i] = INF; read(k[0]); while (k[0]--) { read(a); read(L[a]); } ll ans = 1; for (int i=1; i <= m; i++) { int nL = 0; for (int t=first[i]; t; t=mp[t].next) if (L[mp[t].y] < INF) l[nL++] = L[mp[t].y]; int all = 1 << nL; ll tans = 0; //printf("nL=%d\n", nL); //for (int j=0; j < nL; j++) // printf("%d\n", l[j]); for (int S=0; S < all; S++) { //printf("S=%d\n", S); int touch = calc(S); int K = C(nL, touch); if (touch & 1) K *= -1; ll left = c[i]; for (int j=0; j < nL; j++) if (S & (1 << j)) left -= l[j] + 1; //printf("left=%d C=%lld K=%d\n", left, C(left + k[i] - 1, k[i] - 1), K); tans = (tans + C(left + k[i] - 1, k[i] - 1) * K) % P; } //printf("i=%d tans=%lld\n", i, tans); ans = ans * tans % P; } printf("%lld\n",(ans % P + P) % P); return 0; }