題目描述

一個有N個元素的集合有2^N個不同子集（包含空集），現在要在這2^N個集合中取出若干集合（至少一個），使得它們的交集的元素個數為K，求取法的方案數，答案模1000000007。（是質數喔~）

輸入格式

一行兩個整數N,K

輸出格式

一行為答案。

樣例

樣例輸入

3 2

樣例輸出

6

數據范圍與提示

樣例說明

假設原集合為{A,B,C}

則滿足條件的方案為：{AB,ABC},{AC,ABC},{BC,ABC},{AB},{AC},{BC}

數據說明

對于100%的數據，1≤N≤1000000；0≤K≤N；

思路：

　　做數學題之前一定打個表。。。題解一貫作風，上來不打正解。。。

　　前置知識：一個集合所有的子集個數為2^n每個元素是否出現,那么選子集的方案數為2^(2^n)-1每個集合是否出現，減一是因為一個集合都不選和選空集重了，少算一個。

　　70%算法：DP真他娘的是啥都能干 ，我們不會算集合為n，交集為k的方案，那就設出來啊。。f[n][k]就是答案，f[n][k]=C(n,k)*f[n-k][0],意思是先選出來k個再選交集為0的，那么f[n][0]咋算，它可以從選所有的集合數2^(2^n)-1-f[n][k]得到，然而f[n][k]從之前的f[n-k][0]得到，沒毛病后效性也沒得，他娘的就用你打表了。。（此處借用WD大神代碼）

1 #include<cstdio> 2 #define int long long 3 const long long mod=1000000007; 4 long long fac[1000005],inv[1000005],invv[1000005],x,y,n,k,f0[1000005],f[1000005]; 5 long long pow(long long b,long long t,long long modd,long long ans=1){ 6 for(;t;t>>=1,b=b*b%modd)if(t&1)ans=ans*b%modd; 7 return ans; 8 } 9 signed main(){ 10 scanf("%lld%lld",&n,&k); 11 fac[0]=inv[0]=invv[0]=f0[0]=invv[1]=inv[1]=fac[1]=1;f0[1]=2; 12 for(int i=2;i<=n;++i)fac[i]=fac[i-1]*i%mod,invv[i]=(-mod/i*invv[mod%i])%mod,inv[i]=inv[i-1]*invv[i]%mod; 13 for(int i=1;i<=n;++i){ 14 f0[i]=(pow(2,pow(2,i,mod-1),mod)-1+mod)%mod; 15 for(int j=1;j<=i;++j)f[j]=fac[i]*inv[j]%mod*inv[i-j]%mod*f0[i-j]%mod,f0[i]=(f0[i]-f[j]+mod)%mod; 16 f[0]=f0[i]; 17 } 18 printf("%lld\n",(f[k]+mod)%mod); 19 } View Code

　　100%算法：乖乖打正解，先選k個，n-=k，現在我們要求的就是集合為n，交集為0的方案，這時候我們重新找一個集合的定義（本人思路卒于此），集合A表示包含一個確定元素a的方案的總和，那么會有n個集合向像花一樣綻放，有各種交集例如圖中中間二級重疊不包含E部分表示交集恰有2個的方案。那么我們就要求一級部分的大小（就是要求的無交集的方案），仿佛嗅到了一絲容斥的氣息。。。。交集為0=總-(>=1)+(>=2)-.......

　　ans=Σ(-1)^i*C(n,i)*(2^(2^(n-i))-1);

　　PS：所謂的次方的次方可以用遞推，當然你打兩層快速冪我也沒辦法。。

　　

#include<iostream> #include<cstdio> #include<cmath> using namespace std; const int mn=1e6+20,mod=1e9+7; int f[mn],fac[mn],inv[mn],n,k; int qpow(int x,int k) {int ans=1;for(;k;k>>=1,x=1ll*x*x%mod) if(k&1) ans=1ll*ans*x%mod;return ans; } long long C(int n,int m) {return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;} int main() {scanf("%d%d",&n,&k);fac[0]=1;for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;inv[n]=qpow(fac[n],mod-2);for(int i=n;i;i--) inv[i-1]=1ll*inv[i]*i%mod;long long ans=0,tmp=C(n,k),tp=1;n-=k;int op=(n&1)?-1:1;for(int i=n;~i;i--){ans=(ans+op*C(n,i)*tp%mod)%mod;tp=(tp*tp%mod+2*tp%mod)%mod;op=-op;}ans=ans*tmp%mod;printf("%lld\n",(ans+mod)%mod); } //for sigma i=0->n C(n,i)(2^(2^(n?i))?1) /* g++ 1.cpp -o 1 ./1 4 1 */ View Code

?

轉載于:https://www.cnblogs.com/starsing/p/11129307.html

總結

以上是生活随笔為你收集整理的[BZOJ 2839] 集合计数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。