题解 P3214 【[HNOI2011]卡农】

~~还是科技好用，不动脑子还复杂度优秀~~ 题意相当于是在 $1\cdots n$ 的非空子集中选出 $m$ 个互不相同的，满足这些集合异或起来为空，那么可以按照题意直接写出生成函数: $$ F(x,t)=\prod_{S\neq \varnothing}(1+x^St) $$ 我们要求的就是 $[x^{\varnothing}t^m]F$ 处理集合幂级数自然考虑 FWT(或者说高维 DFT)，那么考虑施加 DFT 后 $T$ 位置上变成了什么，只需对每个 $1+x^St$ 进行 DFT 后乘起来即可. 那么答案就是 $$ \prod_{S\neq \varnothing}(1+(-1)^{|S\cap T|}t) $$ $(-1)^{|S\cap T|}$ 的不同取值只有两种，我们可以分别计数每种情况出现了多少次. 只考虑 $|S\cap T|$ 为偶数的情况，奇数可以简单地用 $2^n-1$ 来减. $$ \sum_i\sum_{S\neq \varnothing}[|S\cap T|=2i]=\sum_i 2^{n-|T|}\binom{|T|}{2i}-1 $$ 当 $|T|\neq 0$ 时，我们知道 $$ \sum_i\binom{|T|}{2i}=\sum_i\binom{|T|}{2i+1}=2^{|T|-1} $$ 这就给出 $$ \prod_{S\neq \varnothing}(1+(-1)^{|S\cap T|}t)=(1+t)^{2^{n-1}-1}(1-t)^{2^{n-1}} $$ 而 $|T|=0$ 时答案是平凡的: $$ (1+t)^{2^n-1} $$ 再逆变换回去，有 $$ [x^{T}]F=\frac{1}{2^n}\sum_S (-1)^{|S\cap T|}[x^S]DFT(F) $$ 在这道题上就是 $$ [x^{\varnothing}t^m]F=\frac{1}{2^n}[t^m]\sum_S[x^S]DFT(F)=\frac{1}{2^n}[t^m]\left((1+t)^{2^n-1}+(2^n-1)(1+t)^{2^{n-1}-1}(1-t)^{2^{n-1}}\right) $$ 前面一项显然就是$\dbinom{2^n-1}{m}$，后面一项可以改写为 $(1-t)(1-t^2)^{2^{n-1}-1}$，按照 $m$ 的奇偶性讨论后可以写为 $(-1)^{\lceil m/2\rceil}\dbinom{2^{n-1}-1}{\lfloor m/2\rfloor}$. 于是问题在于组合数的计算，朴素实现即可 $O(m)$ 完成，存在更加快速的方法（或分块打表阶乘及逆元）. ```cpp #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N=1e6+500,mod=100000007; int ifac[N],n,m; int qpower(int a,int b){int ans=1;for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod;return ans;} int C(int n,int m) { if(n<m)return 0; int ans=ifac[m]; for(int i=0;i<m;i++)ans=1ll*ans*(n-i)%mod; return ans; } int main() { scanf("%d%d",&n,&m);int pw=qpower(2,n-1); ifac[0]=ifac[1]=1;for(int i=2;i<=m;i++)ifac[i]=1ll*(mod-mod/i)*ifac[mod%i]%mod; for(int i=2;i<=m;i++)ifac[i]=1ll*ifac[i-1]*ifac[i]%mod; int ans=0; if(m&1)ans+=(((m+1)>>1&1)?-1:1)*C(pw-1,(m-1)>>1); else ans+=((m>>1&1)?-1:1)*C(pw-1,m>>1); ans=(1ll*ans*(2*pw-1)+C(2*pw-1,m))%mod; ans=1ll*ans*qpower(2*pw,mod-2)%mod; cout<<(ans+mod)%mod<<endl; } ```