湖南集训 Equation

Description

听着自己美妙的曲子,小 Z 进入了梦乡。在梦中,小 Z 仿佛又回到了自己纵横考场的年代。在梦中,小 Z 参加了一场考试,这场考试一共有 n 道题,每道题的最终得分都是一个大于等于 0 的整数。然而醒来后,小 Z 忘记了自己每道题的得分。他只记得自己计算过 m 次一些题目的分数和,每道题都被计算过,并且只被计算过一次。除此之外他还记得其中 t 道题的满分分别是多少(一道题的得分不会超过满分)。现在小 Z 想知道他这场考试有多少种得分情况(至少有一道题的得分不同就算不同的情况),因为这个答案可能很大,你只需要输出答案对 1,000,000,007 取模后的结果即可。

Input

第一行两个整数 n,m 表示题目个数与求和次数。
接下来 m 行,每行以一个整数 k 开头,表示小 Z 这次对 k 道题进行了求和。
然后 k 个整数 a1~ak,表示这次求和的都是哪些题。最后一个整数 c 表示求和后的结果。
一行一个整数 t,含义见题目描述。
t 行,每行两个整数 r,L,表示第 r 道题的满分是 L。

Output

一行一个整数表示答案模 1,000,000,007 的结果。

Sample Input

“`
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

#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;
}

 

 

Show Comments