Count Subsets

题意：

给一集合 $S = \{ 1,2, ... , n \} $，取两个S的子集 A和B，使得A不是B的子集，且B不是A的子集。

解法：

1.牛顿展开

我们采用容斥，显然有

$$ans(n) = (2^n - 1)^2 - 2* \sum_{k=1}^n{C_n^k * (2^k - 2)} - (2^n-1)$$

$$ans(n) = (2^n - 1)(2^n-2) - 2*(\sum_{k=1}^n{C_n^k *2^k} - 2*\sum_{k=1}^n{C_n^k})$$

$$ans(n) = 4^n - 2*3^n + 2^n$$

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <complex>

 #include <cmath>

 #include <ctime> 

 using namespace std;

 #define N 1000010

 #define LL long long

 #define P 1000000007LL

 using namespace std;

 LL power3[N],power2[N];

 int main()

 {

     power3[]=;

     power2[]=;

     for(int i=;i<N;i++)

     {

         power3[i] = power3[i-] * 3LL % P;

         power2[i] = power2[i-] * 2LL % P;

     }

     int T,n;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&n);

         LL ans = power2[n]*(power2[n]+1LL)%P;

         ans = (ans+P-2LL*power3[n]%P)%P;

         printf("%I64d\n",ans);

     }

     return ;

 }

2.生成函数（待补）

可以构造出

巴特西

Count Subsets

最新文章

热门文章