HN省队集训D1T3 Or

生地会考后发现自己连NTT的板子都不会打了….

果然是好久没写代码了…

准备重新学习FFT和NTT和FWT

题意

给定$n,k$,问有多少个长度为n的序列A使得每个元素在$[1,2^k)$中且A的or前缀和序列B是递增序列。

46分$n,k\le 300$

59分$n\le 700,k\le 2000$

100分$n,k\le 3\cdot10^4$

###题解(感谢你群最强之一dkw聚聚的帮助)

注意:以下“位数”指的是为1的二进制位数。

46分

由于$B_i=A_i\ or\ B_{i-1}$,显然B是非严格递增的。

我们只需要每个$A_i$至少有一个二进制位为1而$B_{i-1}$那一位为0。

设$f_i(j)$为长度为i,$B_i$位数为j有多少种方案。
$$
f_i(j)=\sum_{t=0}^{j-1}f_{i-1}(t)2^t\binom{k-t}{j-t}
$$

怎么得到的呢?

枚举$B_{i-1}$的位数t,然后$f_{i-1}(t)$就代表先确定$B_{i-1}$这t位是1,在此基础上,$A_{i}$这t位可以为0或1($2^t$种方案)

然后再在这k-t位里面选出j-t位,使得$A_i$这j-t位是1,另外$n-j$位是0。

$O(nk^2)$

(非常显然是吧)

59分

拆组合数得到
$$
f_i(j)=\sum_{t=0}^{j-1}f_{i-1}(t)2^t\frac{(k-t)!}{(j-t)!(k-j)!}\\
(k-j)!f_i(j)=\sum_{t=0}^{j-1}f_{i-1}(t)2^t\frac{(k-t)!}{(j-t)!}
$$
由于k是常数,我们设$dp_i(j)=(k-j)!f_i(j)$,则柿子可以化成:
$$
dp_i(j)=\sum_{t=0}^{j-1}dp_{i-1}(t)2^t\frac{1}{(j-t)!}
$$
很显然这就是一个卷积的形式了。

记$F_j=dp_i(j),G_j=dp_{i-1}(j)2^j,H_j=\frac{1}{j!}$

显然$H_0=0$

那么$F=G\ast H$

$O(nk\log k)$

100分

考虑生成函数,设$A_i(x)=\sum_{j=0}^\infty dp_i(j)x^j$,$B(x)=\sum_{i=1}^\infty \frac{1}{i!}x^i=(e^x-1)$

所以
$$
A_n(x)=A_{n-1}(2x)B(x)=A_0(x^n)\prod_{i=0}^{n-1} B(2^ix)=k!\prod_{i=0}^{n-1}(e^{2^ix}-1)
$$
设$A_n(x)=\prod_{i=0}^{n-1}(e^{2^ix}-1)$

考虑分治计算:

如果$n$为奇数,则$A_n(x)=A_{n-1}(x)(e^{2^{n-1}}-1)$

否则$A_n(x)=A_{\frac{n}{2}}(x)A_\frac{n}{2}(2^{\frac{n}{2}}x)$

计算的时候,需要$\bmod x^{k+1}$,只能通过拿两个k次多项式卷积以后,把后面的项删去就又只有k次了

时间复杂度$O(k\log n\log k)$

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
115
116
117
118
119
120
121
122
123
124
125
/*
Author: CNYALI_LK
LANG: C++
PROG: or.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;

const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
ll s=0,base=1;
char c;
while(!isdigit(c=getchar()))if(c=='-')base=-base;
while(isdigit(c)){s=s*10+(c^48);c=getchar();}
return s*base;
}
const ll p=998244353;

ll fac[102423],inv[102423],invf[102423],p2[102423];
ll C(ll n,ll k){
return fac[n]*invf[k]%p*invf[n-k]%p;
}
ll fpm(ll a,ll b){
ll c=1;
while(b){
if(b&1)c=a*c%p;
a=a*a%p;
b>>=1;
}
return c;
}
ll n,m,f[102423],g[102423],rev[102423],s,t,omega[102423],reo[102423];
void FFT(ll *f,ll flag){
for(ll i=0;i<s;++i)if(i<rev[i])swap(f[i],f[rev[i]]);
for(ll i=1;i<s;i<<=1){
ll w=flag>0?omega[i]:reo[i];
for(ll j=0;j<s;j+=i+i){
ll aw=1,xa,xb;
for(ll k=0;k<i;++k){
xa=f[j+k],xb=aw*f[j+k+i]%p;
f[j+k]=(xa+xb)%p;
f[j+k+i]=(xa-xb+p)%p;
aw=aw*w%p;
}
}
}
if(flag<0){
for(ll i=0;i<s;++i)f[i]=f[i]*inv[s]%p;
}
}
void calc(ll n){
if(n==1){
for(ll i=1;i<=m;++i)f[i]=invf[i];
return;
}
if(n&1){
calc(n-1);
for(ll i=0;i<s;++i)g[i]=0;
ll pow2=1;
for(ll i=1;i<=m;++i){pow2=pow2*p2[n-1]%p;g[i]=invf[i]*pow2%p;}
FFT(f,1);
FFT(g,1);
for(ll i=0;i<s;++i)f[i]=f[i]*g[i]%p;
FFT(f,-1);
f[0]=0;
for(ll i=m+1;i<s;++i)f[i]=0;
}
else{
calc(n>>1);
for(ll i=0;i<s;++i)g[i]=0;
ll pow2=1;
for(ll i=1;i<=m;++i){pow2=pow2*p2[n>>1]%p;g[i]=pow2%p*f[i]%p;}
FFT(f,1);
FFT(g,1);
for(ll i=0;i<s;++i){
f[i]=f[i]*g[i]%p;
}
FFT(f,-1);
for(ll i=m+1;i<s;++i)f[i]=0;
}
}
int main(){
freopen("or.in","r",stdin);
freopen("or.out","w",stdout);
n=read();m=read();
for(s=1;s<=m;s<<=1,++t);
s<<=1;
omega[s>>1]=fpm(3,998244352/s);
reo[s>>1]=fpm(omega[s>>1],998244351);
for(ll i=s>>2;i;i>>=1){
omega[i]=omega[i<<1]*omega[i<<1]%p;
reo[i]=reo[i<<1]*reo[i<<1]%p;
}
for(ll i=1;i<s;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<t);
fac[0]=fac[1]=inv[1]=invf[0]=invf[1]=1;
p2[0]=1;p2[1]=2;
for(ll i=2;i<=s;++i){
fac[i]=fac[i-1]*i%p;
inv[i]=(p-p/i)*inv[p%i]%p;
invf[i]=invf[i-1]*inv[i]%p;
p2[i]=(p2[i-1]<<1)%p;
}
calc(n);
ll ans=0;
for(ll i=1;i<=m;++i)ans=(ans+f[i]*invf[m-i]%p*fac[m])%p;
printf("%lld\n",ans);
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×