它们的交集的元素个数为K,求取法的方案数,答案模1000000007.(是质数喔~)
对于100%的数据,1≤N≤1000000;0≤K≤N;
一看正解,连状态数组都不用,让我想到了10.9考试 第一题建造城市的打法.
我们同样,先从n个数里提前选出k个数,然后去枚举多出来的集合的交集至少是多少,仍然奇减偶加,假设我们当前要求的是交集多出至少为x的方案数,那么就是:
在(2^(2^(n-k-x))-1)即表示在除去k+x个数后的2^(n-k-x)集合中选集合的方案数,由于我们不能一个都不选,所以还得减去全部不选的情况.C(n-kx)就是在剩下n-k个数中选出x个数的方案数,最后在将总和乘以在n个数中选k个数的方案数.