正题
题目链接:https://www.luogu.com.cn/problem/P3214
题目大意
一个由\(1\sim n\)的所有整数构成的集合\(S\)，求出它的\(m\)个不同非空子集满足每个元素都出现了偶数次。
解题思路
集合的话不用考虑顺序，可以输出有序的答案除以\(m!\)就好了。
选\(i\)个的话，考虑偶数次的条件，无论前面\(i-1\)个集合如何选取，最后一个都能根据情况调整过来，所以不考虑重复的话方案就是\(P_{2^n}^{i-1}\)
设\(f_i\)表示选出\(i\)个集合的答案，因为上面那种方案可能会导致最后一个集合出现重复等问题，我们要减去不合法的。
首先有可能是空集，那么表示前面\(i-1\)个集合都是合法的，所以方案是\(f_{i-1}\)。然后是重复，考虑和它重复的集合\(j\)，那么剩下\(i-2\)个就是合法的，然后这两个重复的集合有\(2^n-(i-2)-1\)种取值（减去空集和前面出现过的），方案就是\(f_{i-2}\times (i-1)\times(2^n-i+1)\)
所以方程就是
\[f_i=P_{2^n}^{i-1}-f_{n-1}-f_{n-2}\times(i-1)\times(2^n-i+1)
\]
\(O(n)\)转移即可。
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=1e6+10,P=1e8+7;
ll n,m,A[N],f[N];
ll power(ll x,ll b){
ll ans=1;
while(b){
if(b&1)ans=ans*x%P;
x=x*x%P;b>>=1;
}
return ans;
}
signed main()
{
scanf("%lld%lld",&m,&n);ll p=1;
for(ll i=1;i<=m;i++)p=p*2ll%P;
ll fac=1;A[0]=1;
for(ll i=1;i<=n;i++)
A[i]=A[i-1]*(p-i)%P,fac=fac*i%P;
f[0]=1;
for(ll i=2;i<=n;i++)
f[i]=(A[i-1]-f[i-1]-f[i-2]*(i-1)%P*(p-i+1)%P)%P;
f[n]=f[n]*power(fac,P-2)%P;
printf("%lld\n",(f[n]+P)%P);
return 0;
}