它们的交集的元素个数为K,求取法的方案数,答案模1000000007.(是质数喔~)
对于100%的数据,1≤N≤1000000;0≤K≤N;
恰好xx的问题,很大几率是容斥.
冷静分析一下,我们现在假设钦定了K个数字作为交集的最终结果,那么包含这些数字数字组成的集合就可以随便选,这样的方案数是\(C(nk)*(2^{2^{n-i}}-1)\)(这里空集是不合法的).但是这样算出来的是"至少有K个",我们要用容斥来处理一下,而且这里的方案是有序的,所以容斥系数是还要乘以组合数.具体地,恰好选j个的每个方案里面,都包含了\(C(ji)\)个有i个的,要算入系数.