壹、题目描述 ¶
贰、题解 ¶
\[\newcommand\down[2]{{{#1}^{\underline{#2}}}} \]先不考虑集合的无序性，这样只需要最后 \(\div m!\) 即可。
记 \(f(i)\) 为选择 \(i\) 个合法集合的方案数。
注意到只要我们选择了前 \(i-1\) 的集合，最后一个集合就已经被确定了。
故而，我们从 \(S=2^n-1\) 个集合（排除空集）中选择 \(i-1\) 个（有序），方案数即 \(\down{S}{i-1}\)，不过有两个问题：
- 如果前面的集合刚好全为偶数了，那么最后一个集合就*选择了一个空集；
- 最后一个集合可能和前面的集合选择相同；
对于第一种，注意到前面的状态实际上就是 \(f(i-1)\)，对于第二种，不难发现，如果将最后一个集合和与之相同的集合匹配，剩下的 \(i-2\) 个集合又刚好是 \(f(i-2)\)，所以，我们就有递推式：
\[f(i)=\down{S}{i-1}-f(i-1)-(i-1)(S-(i-2))f(i-2) \]至于 \(f(i-2)\) 的系数，事实上就是先选择一个集合与之相同，然后再选择他们长什么样子。
边界情况，\(f(0)=1\)，然后我们就可以递推了。
叁、参考代码 ¶
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
#define NDEBUG
#include<cassert>
namespace Elaina{
#define rep(i, l, r) for(int i=(l), i##_end_=(r); i<=i##_end_; ++i)
#define drep(i, l, r) for(int i=(l), i##_end_=(r); i>=i##_end_; --i)
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)
#define Endl putchar('\n')
#define mmset(a, b) memset(a, b, sizeof a)
// #define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T>inline T fab(T x){ return x<0? -x: x; }
template<class T>inline void getmin(T& x, const T rhs){ x=min(x, rhs); }
template<class T>inline void getmax(T& x, const T rhs){ x=max(x, rhs); }
template<class T>inline T readin(T x){
x=0; int f=0; char c;
while((c=getchar())<'0' || '9'<c) if(c=='-') f=1;
for(x=(c^48); '0'<=(c=getchar()) && c<='9'; x=(x<<1)+(x<<3)+(c^48));
return f? -x: x;
}
template<class T>inline void writc(T x, char s='\n'){
static int fwri_sta[1005], fwri_ed=0;
if(x<0) putchar('-'), x=-x;
do fwri_sta[++fwri_ed]=x%10, x/=10; while(x);
while(putchar(fwri_sta[fwri_ed--]^48), fwri_ed);
putchar(s);
}
}
using namespace Elaina;
const int maxn=1e6;
const int mod=1e8+7;
inline int qkpow(int a, int n){
int ret=1;
for(; n>0; n>>=1, a=1ll*a*a%mod)
if(n&1) ret=1ll*ret*a%mod;
return ret;
}
int n, m, S, fac=1;
int f[maxn+5], A[maxn+5];
signed main(){
n=readin(1), m=readin(1);
S=(qkpow(2, n)+mod-1)%mod;
f[0]=1, f[1]=0, A[0]=1;
for(int i=1; i<=m; ++i)
A[i]=1ll*A[i-1]*(S+mod-i+1)%mod;
for(int i=2; i<=m; ++i){
f[i]=(A[i-1]+mod-f[i-1]+mod-1ll*(i-1)*(S+mod-i+2)%mod*f[i-2]%mod)%mod;
fac=1ll*fac*i%mod;
// printf("f[%d] == %d, fac == %d\n", i, f[i], fac);
}
writc(1ll*f[m]*qkpow(fac, mod-2)%mod);
return 0;
}
肆、另附 ¶
记得曾经也做过类似的题的，在这里，两个都利用到了异或的特殊性质，虽然在这道题中没有把异或点明，不过奇偶已经很像异或了。
另外，将无序的集合分离出去也是十分重要的一步，不然后面的容斥将十分复杂。