「LOJ #6358」前夕

Problem

Description

给定 n,m ,求在 \left\{1, 2, \dots, n\right\} 的所有 2^{n} 个子集中选出若干个使其交集大小为 m 的倍数的方案数。
答案对 998244353 取模。

Constraints

1\le n\le 10^{7},m = 4

Solution

学到了新科技。。。

orz Sdchr.

Analysis

考虑容斥。
易知选择若干个集合使其交集大小 \ge k 的方案数为 \displaystyle{\binom{n}{k}\left(2^{2^{n-k}}-1\right)}
设容斥系数为 f(k) ,则答案为:

\sum_{k=0}^{n}f(k)\binom{n}{k}\left(2^{2^{n-k}}-1\right)

考虑选取若干个集合使其交集大小为 k 的方案被计算的次数,有等式:

\sum_{i=0}^{k}\binom{k}{i}f(i)=\left[k\equiv 0\pmod{m}\right]=\left[m | k\right]

二项式反演可得:

f(k)=\sum_{i=0}^{k}(-1)^{k-i}\binom{k}{i}\left[m | i\right]

w_{m} m 次单位根,则易有性质:

\frac{1}{m}\sum_{i=0}^{m-1}\left(w_{m}^{k}\right)^{i}=\left[k\equiv 0\pmod{m}\right]=\left[m | k\right]

故:

\begin{aligned} f(k)&=\sum_{i=0}^{k}(-1)^{k-i}\binom{k}{i}\left[m | i\right]\\ &=\sum_{i=0}^{k}(-1)^{k-i}\binom{k}{i}\frac{1}{m}\sum_{j=0}^{m-1}\left(w_{m}^{i}\right)^{j}\\ &=\frac{1}{m}\sum_{i=0}^{m-1}\sum_{j=0}^{k}\binom{k}{j}(-1)^{k-j}w_{m}^{ij}\\ &=\frac{1}{m}\sum_{i=0}^{m-1}\left(w_{m}^{i}-1\right)^{k} \end{aligned}

求出所有 f(k) 直接计算答案即可。

时间复杂度 O(nm)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<cstdio>

using i64=long long;
using uchar=unsigned char;

constexpr int maxn(10000000);
constexpr int p(998244353);
constexpr int wn[]={0,911660634,998244351,86583717};

inline int io(){
static int _;
return scanf("%d",&_),_;
}

template<typename _Tp>
inline int div2(const _Tp&v)
{return((v&1)?v+p:v)>>1;}

template<typename _Tp>
inline int fpow(_Tp v,int n){
int pw=1;
for(;n;n>>=1,v=(i64)v*v%p)
if(n&1)pw=(i64)pw*v%p;
return pw;
}

int invFac[maxn+1];
i64 f[maxn+1];

int main(){
const int n(io());

int v=1;
for(int i=2;i<=n;++i)
v=(i64)v*i%p;

const int facn=v;
invFac[0]=invFac[1]=1;
v=fpow(v,p-2);
for(int i=n;i!=1;--i)
invFac[i]=v,
v=(i64)v*i%p;

int w[]={0,wn[1],wn[2],wn[3]};
f[0]=4;
for(int k=1;k<=n;++k){
f[k]=(i64)w[1]+w[2]+w[3];
w[1]=(i64)w[1]*wn[1]%p;
w[2]=(i64)w[2]*wn[2]%p;
w[3]=(i64)w[3]*wn[3]%p;
}

i64 ans=0;
for(int k=n,pw=2;~k;--k,pw=(i64)pw*pw%p)
ans+=(i64)f[k]%p*(pw-1)%p*invFac[k]%p*invFac[n-k]%p;

printf("%d",div2(div2(ans%p*facn%p+4)));

return 0;
}