http://acm.zju.edu.cn/onlinejudge/showProblem.do?

problemId=4535

一个集合s有n个元素，求满足这种集合序列{s1,s2....sk}使S₁ ∩
S₂ ∩ ... ∩ S_k =
∅。si是s的子集。

从每一个元素考虑会使问题变得简单。

首先n个元素是相互独立的，单独考虑第i个元素，它在k个子集的全部情况是2^k，当中有一种情况是k个子集都有第i个元素，这一种情况正好不是我们想要的，所以合法的应该是2^k-1。那么n个元素就是( 2^k-1 )^n。

#include <stdio.h>

#include <iostream>

#include <map>

#include <set>

#include <bitset>

#include <list>

#include <stack>

#include <vector>

#include <math.h>

#include <string.h>

#include <queue>

#include <string>

#include <stdlib.h>

#include <algorithm>

//#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\n",res);

    }

    return 0;

}