2024年6月杂题乱写
P3214 [HNOI2011] 卡农
设 \(f_i\) 表示选了 \(m\) 个集合的答案，简单观察发现，只要确定了 \(m-1\) 个集合，最后一个集合就是确定的，不是偶数次数的出现，偶数次数的不出现，选 \(m\) 个集合有 \(C_{2^n-1}^{m-1}\) 种方案，考虑下面两种不合法的情况。
- 这 \(m-1\) 个集合已经合法，最后一个集合为空集。
- 最后要选的集合在前面 \(m-1\) 个集合出现过。
答案就是总数减去这两种情况，第一种情况显然为 \(f_{i-1}\)，第二种情况其实就是有 \(i-2\) 个集合已经合法了，数量为 \(f_{i-2}\)，但是因为最后的一个集合（相同的两个）不确定，所以第二种情况实际上有 \(f_{i-2}\cdot[2^{n}-1-(i-2)]\)，直接减去就可以，这时因为我们每一种都算了 \(m\) 遍，所以答案要除以 \(m\)。
\[f_i=\frac{C_{2^n-1}^{i-1}-f_{i-1}-f_{i-2}\cdot (2^n-i+1)}{m}
\]
直接递推即可。
#include<bits/stdc++.h>
#define int long long
inline int read(){
char ch=getchar();int x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
const int N=1e6+10,mod=1e8+7;
inline int mo(int x){return x<0?(x%mod+mod)%mod:(x>=mod?x%mod:x);}
inline int qpow(int a,int b){
int res=1;
for(;b;b>>=1,a=mo(a*a))if(b&1)res=mo(res*a);
return res;
}
int n,m,sum,inv[N],C,f[N];
signed main(){
// freopen("in.in","r",stdin),freopen("out.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0),std::cout.tie(0);
n=read(),m=read();sum=mo(qpow(2,n)-1);
if(m>sum){std::cout<<0<<'\n';exit(0);}
inv[1]=1,f[1]=f[2]=0;f[0]=1;
for(int i=2;i<=m;++i)inv[i]=mo((mod-mod/i)*inv[mod%i]);
C=mo(mo(sum*(sum-1))*inv[2]);
for(int i=3;i<=m;++i){
f[i]=mo(mo((C-f[i-1]-mo(f[i-2]*mo(sum-i+2))))*inv[i]);
C=mo(mo(C*(sum-i+1))*inv[i]);
}
std::cout<<f[m]<<'\n';
}