[2018HN省队集训D1T3] Or
题意
给定 $n$ 和 $k$, 求长度为 $n$ 的满足下列条件的数列的数量模 $998244353$ 的值:
- 所有值在 $[1,2^k)$ 中
- 前缀或的值严格递增
$n,k\le 3\times 10^4$
题解
这题有点意思
首先肯定每一项都得有新出现的二进制位, 于是可以想到一个超简单的 $O(nk^2)$ 的DP, 设 $dp_{i,j}$ 为长度为 $i$ 且已经出现了 $j$ 个二进制位的数列的个数. 然后考虑枚举数列第 $i$ 项的新二进制位个数, 那么转移显然:
$$
dp_{i,j}=\sum_{k=1}^j {j\choose k} dp_{i-1,j-k}2^{j-k}
$$
统计答案的时候枚举总共出现的二进制位个数:
$$
\text{Ans}=\sum_{i=1}^k{k\choose i}dp_{n,i}
$$
状态数是 $O(nk)$ 的, 朴素转移 $O(k)$, 总复杂度 $O(nk^2)$.
机智的我们一眼看出后面的转移式子就是个二项卷积, 随手比个阶乘打个NTT上去就变成 $O(nk\log k)$ 了.
然而这还不够.
我们发现一次转移相当于一次卷积和一次点积, 我们肯定想这玩意能不能快速幂一发.
然后我们非常sad地发现由于里面那个 $2^{j-k}$ 搞事情所以不能裸快速幂.
考虑这个 $2^{j-k}$ 是拿来干啥的. $k$ 是第 $i$ 项的新二进制位个数, $j$ 是前 $i$ 项已经出现过的二进制位个数, $j-k$ 是前 $i-1$ 项已经出现的二进制位个数. 显然这些前 $i-1$ 项中出现过的二进制位在第 $i$ 项中是任选的, 于是我们需要乘上这玩意.
那么如果转移不是 $1$ 位而是 $m$ 位呢?
这次应该是这样的转移式:
$$
dp_{i,j}=\sum_{k=1}^j{j\choose k} dp_{i-m,j-k}dp_{m,k}2^{(j-k)m}
$$
我们相当于在一个长度为 $i-m$ 的序列后面接了长度为 $m$ 的序列并用组合数让他们的二进制位互不干扰. 但是后面接的长度为 $m$ 的数列里面是完全不包含前面 $i-m$ 中的二进制位的方案的. 这些位由于在前面已经出现过, 所以在后面长度为 $m$ 的数列里是任选的. 一共有 $m(j-k)$ 位.
下标相同的并在一起就又是个二项卷积了, 倍增就好了. 复杂度 $O(k \log k \log n)$.
参考代码
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
#include <bits/stdc++.h>
const int G=3;
const int DFT=1;
const int IDFT=-1;
const int MAXN=1e5+10;
const int MOD=998244353;
const int PHI=MOD-1;
int n;
int k;
int dp[MAXN];
int pw[MAXN];
int tr[MAXN];
int tx[MAXN];
int rev[MAXN];
int fact[MAXN];
int C(int,int);
int Pow(int,int,int);
void NTT(int*,int,int);
int main(){
scanf("%d%d",&n,&k);
pw[0]=1;
fact[0]=1;
for(int i=1;i<=k;i++){
pw[i]=(pw[i-1]<<1)%MOD;
fact[i]=1ll*fact[i-1]*i%MOD;
tr[i]=Pow(fact[i],MOD-2,MOD);
}
int bln=1,bct=0;
while(bln<=k*2){
bln<<=1;
++bct;
}
for(int i=0;i<bln;i++)
rev[i]=(rev[i>>1]>>1)|((i&1)<<(bct-1));
NTT(tr,bln,DFT);
dp[0]=1;
int cur=1;
while(n>0){
if(n&1){
for(int i=k+1;i<bln;i++)
dp[i]=0;
for(int i=0;i<=k;i++)
dp[i]=1ll*dp[i]*Pow(pw[i],cur,MOD)%MOD;
NTT(dp,bln,DFT);
for(int i=0;i<bln;i++)
dp[i]=1ll*dp[i]*tr[i]%MOD;
NTT(dp,bln,IDFT);
}
NTT(tr,bln,IDFT);
for(int i=k+1;i<bln;i++)
tx[i]=0;
for(int i=0;i<=k;i++)
tx[i]=1ll*tr[i]*Pow(pw[i],cur,MOD)%MOD;
NTT(tx,bln,DFT);
NTT(tr,bln,DFT);
for(int i=0;i<bln;i++)
tr[i]=1ll*tr[i]*tx[i]%MOD;
NTT(tr,bln,IDFT);
for(int i=k+1;i<bln;i++)
tr[i]=0;
NTT(tr,bln,DFT);
n>>=1;
cur<<=1;
}
int ans=0;
for(int i=0;i<=k;i++)
(ans+=1ll*dp[i]*fact[i]%MOD*C(k,i)%MOD)%=MOD;
printf("%d\n",ans);
return 0;
}
int C(int n,int m){
return n<0||m<0||n<m?0:1ll*fact[n]*Pow(fact[m],MOD-2,MOD)%MOD*Pow(fact[n-m],MOD-2,MOD)%MOD;
}
void NTT(int* a,int len,int opt){
for(int i=0;i<len;i++)
if(rev[i]>i)
std::swap(a[i],a[rev[i]]);
for(int i=1;i<len;i<<=1){
int step=i<<1;
int wn=Pow(G,(opt*PHI/step+PHI)%PHI,MOD);
for(int j=0;j<len;j+=step){
int w=1;
for(int k=0;k<i;k++,w=1ll*w*wn%MOD){
int x=a[j+k];
int y=1ll*a[j+k+i]*w%MOD;
a[j+k]=(x+y)%MOD;
a[j+k+i]=(x-y+MOD)%MOD;
}
}
}
if(opt==IDFT){
int inv=Pow(len,MOD-2,MOD);
for(int i=0;i<len;i++)
a[i]=1ll*a[i]*inv%MOD;
}
}
inline int Pow(int a,int n,int p){
int ans=1;
while(n>0){
if(n&1)
ans=1ll*a*ans%p;
a=1ll*a*a%p;
n>>=1;
}
return ans;
}
|
