心路:

{

想了個(gè)思路打出來硬干掉了樣例，然后發(fā)現(xiàn)是錯(cuò)的....
當(dāng)時(shí)直接崩了...煩躁滴很
...其實(shí)這個(gè)思路和題解大方向上是一樣的，想到了用至少含k個(gè)的方案數(shù)減去含k+1個(gè)的加上k+2的。。。

然后再想怎么求至少含k個(gè)的方案數(shù)想到了讓集合含這k個(gè)數(shù)然后隨機(jī)組就行，但沒有想出來怎么求含這k個(gè)數(shù)的集合數(shù)，而且就算求出來發(fā)現(xiàn)不能直接對(duì)一種情況乘，有重復(fù)計(jì)算的...

想到這...再想...再想...放棄->頹題解。T_T
頹完題解，發(fā)現(xiàn)我是把題目信息忽略了...2^n沒怎么用上;

}

題解

{

　　往容斥上想，容斥的一般思路就是先找出單一滿足的，把問題簡單化（讓其限制變小），再逐步用容斥求解。

這題總思路就是先找至少含k個(gè)的（限制變少，能夠推式），再容斥。

再求至少含k個(gè)的時(shí)候，容易發(fā)現(xiàn)想要交出含這k個(gè)的，讓集合含這k個(gè)數(shù)在隨機(jī)組合一定能交出來.

問題來了：怎么求含特定k個(gè)數(shù)的集合總數(shù)呢？

把這k個(gè)數(shù)提取出來剩下的數(shù)隨機(jī)組，能夠組成的集合在把k個(gè)數(shù)補(bǔ)回去不就是答案嗎，所以有2^(n-k)種（含空集，實(shí)際指的是正好只含這K個(gè)數(shù)的集合），在讓這幾個(gè)集合隨機(jī)組一定是滿足能交成至少含k個(gè)數(shù)的方案。注意空集不是，所以是2^( 2^(n-k) )-1種。

舉個(gè)栗子：數(shù)據(jù)是4 2

以1,3為例，把1 3提取，剩下的數(shù)所組是{2},{4},{2,4},{空}，其實(shí)就是{1,2,3},{1,3,4},{1,2,3,4},{1,3};這四個(gè)集合在隨機(jī)組成的方案中，空集相當(dāng)于哪個(gè)集合都沒取交集為空所以不符合。

求出1,3后乘上C（n,2）不就是交出來至少含k個(gè)的方案數(shù)了嗎？顯然不是，，，有重復(fù)的啊

比如1,3會(huì)求到{1,2,3,4}交{1,3,4},而1,4..3,4也會(huì)（當(dāng)時(shí)我就這崩了...）

看重復(fù)的有多少啊->對(duì)于求k個(gè)時(shí)交出來是k+1個(gè)的會(huì)算C（k+1,k）遍以此類推..所以在容斥時(shí)只要把重復(fù)的倍數(shù)減去就行。

設(shè)f(k)=C(n,k)*(? 2^( 2^(n-k) )-1 ),

答案就是f(k)*C(K,K)-C(K+1,K)*f(k+1)+C(k+2,k)*f(k+2)...;

預(yù)處理階乘和逆元,2^...這里也要預(yù)處理不然會(huì)WA（我也不知道為哈用快速冪求出的大數(shù)據(jù)就是不對(duì)）。

2^(2^(n-k))=( 2^(2^(n-k-1)) )^2,利用這個(gè)性質(zhì)倒推預(yù)處理出來就行了

f(k)?Ckk?f(k+1)?Ckk+1+f(k+2)?Ckk+2...f(n)?Ckn

}

#include<cstdio> #include<iostream> using namespace std; #define ll long long const int mod=1e9+7; const int maxn=1000010; int n,k; ll ans,f[maxn]; ll fac[maxn],inv[maxn],qtwo[maxn]; ll qpow(ll a,int b) {ll ans=1;while(b){if(b&1) ans=ans*a%mod;b>>=1;a=a*a%mod;}return ans; } void init() {fac[0]=1;for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;inv[n]=qpow(fac[n],mod-2);for(int i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;qtwo[n]=2;for(int i=n-1;i>=0;i--) qtwo[i]=qtwo[i+1]*qtwo[i+1]%mod; } void F(int x) {ll turn,kp;turn=qtwo[x]-1;f[x]=fac[n]*inv[x]%mod*inv[n-x]%mod*turn%mod; } void rongchi() {for(int i=k;i<=n;i+=2) ans=(ans+ fac[i]*inv[k]%mod*inv[i-k]%mod*f[i]%mod )%mod;for(int i=k+1;i<=n;i+=2) ans=(ans+mod- fac[i]*inv[k]%mod*inv[i-k]%mod*f[i]%mod )%mod; } int main() { //freopen("c.out","w",stdout);scanf("%d%d",&n,&k);init();for(int i=k;i<=n;i++) F(i);rongchi();printf("%lld",ans); } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/three-D/p/11138164.html

總結(jié)

以上是生活随笔為你收集整理的集合计数 （容斥原理）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。