题意：在 \(2^n\) 个集合中选择若干集合，选择的集合的公共部分大小为 \(4\) 的倍数的方案数是多少。
首先肯定先枚举交集啊。
\[\sum_{i=0}^{n}[4\mid n]F(i)
\]
其中 \(F(i)\) 为从 \(2^n\) 个集合中选取的集合交集大小为 \(i\) 的方案数。
这个一看好像挺二项式反演。
设 \(G(i)\) 为钦定 \(i\) 个位置相同，剩下位置乱填的方案数。
\[F(k)=\sum_{i=k}^{n}\binom{n}{i}(-1)^{i-k}G(i)=\sum_{i=k}^{n}\binom{n}{i}(-1)^{i-k}\binom{i}{k}(2^{2^{n-i}}-1)
\]
\[\sum_{i=0}^{n}\sum_{j=i}^{n}\binom{n}{j}\binom{j}{i}(2^{2^{n-j}}-1)(-1)^{i-j}[4\mid i]
\]
\[\sum_{j=0}^{n}\binom{n}{j}(2^{2^{n-j}}-1)\sum_{i=0}^{j}\binom{j}{i}(-1)^{i-j}[4|i]
\]
\[\frac{1}{4}\sum_{k=0}^{3}\sum_{i=0}^{n}\binom{n}{i}(2^{2^{n-i}}-1)\sum_{j=0}^{i}\binom{i}{j}(-1)^{i-j}w^{jk}
\]
\[\frac{1}{4}\sum_{k=0}^{3}\sum_{i=0}^{n}\binom{n}{i}(2^{2^{n-i}}-1)(-1)^i\sum_{j=0}^{i}\binom{i}{j}(-w^k)^j
\]
\[\frac{1}{4}\sum_{k=0}^{3}\sum_{i=0}^{n}\binom{n}{i}(2^{2^{n-i}}-1)(w^k-1)^i
\]
\(O(4n)\) 搞定。
不是 \(4\) 的倍数的时候需要加一。我也不知道为什么是对的，可他就是过了.jpg
#include<cstdio>
typedef unsigned ui;
const ui M=1e7+5,mod=998244353;
ui n,c[M],ifac[M];
inline ui Solve(const ui&x){
ui ans(0);for(ui i=0,y(1);i<=n;++i,y=1ull*y*x%mod)ans=(ans+1ull*ifac[i]*ifac[n-i]%mod*c[n-i]%mod*y)%mod;
return ans;
}
signed main(){
ui y(911660635),x(1),C(1),ans(0);scanf("%u",&n);
ifac[0]=ifac[1]=1;c[0]=2;c[1]=4;
for(ui i=2;i<=n;++i){
ifac[i]=1ull*(mod-mod/i)*ifac[mod%i]%mod;c[i]=1ull*c[i-1]*c[i-1]%mod;C=1ull*C*i%mod;
}
for(ui i=1;i<=n;++i)ifac[i]=1ull*ifac[i-1]*ifac[i]%mod;
for(ui i=0;i<4;++i,x=1ull*x*y%mod)ans=(ans+Solve(x-1))%mod;printf("%u",748683265ull*ans%mod*C%mod+bool(n%4));
}