程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> zoj How Many Sets I(組合計數)

zoj How Many Sets I(組合計數)

編輯:C++入門知識

zoj How Many Sets I(組合計數)


 

一個集合s有n個元素,求滿足這樣的集合序列{s1,s2....sk}使S1 ∩ S2 ∩ ... ∩ Sk = ∅,si是s的子集。

 

從每個元素考慮會使問題變得簡單。首先n個元素是相互獨立的,單獨考慮第i個元素,它在k個子集的所有情況是2^k,其中有一種情況是k個子集都有第i個元素,這一種情況正好不是我們想要的,所以合法的應該是2^k-1,那麼n個元素就是( 2^k-1 )^n。

 

 

#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#define LL __int64
#define LL long long
#define ULL unsigned long long
#define eps 1e-9
#define PI acos(-1.0)
using namespace std;

const LL mod = 1000000007;

LL Pow(LL a, LL b)
{
    LL res = 1;
    while(b)
    {
        if(b&1)
            res = (res*a)%mod;
        b >>= 1;
        a = (a*a)%mod;
    }
    return res;
}

int main()
{
    LL n,k;
    while(~scanf(%lld %lld,&n,&k))
    {
        LL res = Pow((LL)2,k);
        res -= 1;
        res = Pow(res,n);
        printf(%lld
,res);
    }
    return 0;
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved