RainAir
My OI Blog
RainAir
「CF623E」 Transforming Sequence

题目链接

没想到非 Chinese Round 也会出这么毒瘤的题目……

题目大意:对于正整数序列 $A$,定义序列 $B$: $B_1=A_1,B_i=B_{i-1}\ or\ A_i,i\in[2,n]B $ 其中 or 为位或运算。 每一个序列合法,满足对于$ \forall i\in[1,n]$,有 $A_i\in[1,2^k])$ 而且对于 $\forall i\in[2,n]$,有$B_i>B_{i-1}$。 给出 $n(n \leq 10^{18}),k(k \leq 3* 10^4)$ ,求合法序列数。

对 $10^9 + 7$ 取模

首先我们观察到每次至少要多一个变成 $1$ 的二进制位否则不可能满足要求。

所以我们按照这个,自然地考虑动态规划:

设 $F_{i,j}$ 表示已经选择了 $i$ 个数,已经有 $j$ 位变成了 $1$ 的方案数。首先观察到如果这样设的话会超时,所以我们考虑如何把转移写成卷积的形式。我们考虑如何用已知的值更新 $f_{x+y,i}$。

我们设 $j \in [1,i]$。这个 $x$ 和 $y$ 的枚举实质就是枚举那部分钦定那部分不钦定,所以前 $x$ 个数中选择 $j$ 位的方案显然是 $(^i_j) \times f_{x,j}$(组合数是考虑在 $i$ 个二进制位中任选 $j$ 个)。后 $y$ 个数中需要选择 $i-j$ 位,方案数为 $f_{y,i-j}$,然后我们考虑这些前面 $x$ 个数钦定了 $j$ 个位置,那么剩下的 $y$ 个数上在这 $j$ 个位置上可以随便填(因为或运算保证已经有一个是 $1$ 了),所以需要再乘上一个 $(2^{j})^{y}$。

转移方程大概如下:

$$f_{x+y,i} = \sum_{j=1}^i f_{x,j} \times (^i_j) \times f_{y,i-j} \times (2^{j})^y$$

通过小学就学习过的基本变换,不难得到:

$$f_{x+y,i} = i! \times \sum_{j=1}^i \frac{f_{x,j} \times (2^{j})^y }{j!} \times \frac{f_{y,i-j}}{(i-j)!}$$

现在我们就可以用卷积优化转移了,不过还需要处理两个小问题。
1. $10^9 + 7$ 不是个 NTT 模数哎怎么办呢?

有个科技叫做任意模数 NTT(MTT),建议大家去点一下。

我们考虑两个多项式做乘法,不能用 FFT 的原因是数字过大会爆精度。不如考虑把每个多项式写成 $A_{1} \times pp + A_{2}$,取 $pp = \sqrt{p} $。这样两个多项式 $A,B$ 相乘就转化为了求 $(A_{1} \times pp + A_{2}) \times (B_{1} \times pp + B_{2})$。

展开可得:$A_{1} \times B_{1} \times pp^2 + (A_1 \times B_2 + A_2 \times B_1) \times pp + A_2 \times B_2$。多做几遍 DFT 最后在外面取模就好了。不过貌似有国家队神仙提出了四遍 DFT 做法但是我不会。
2. 这个 $n$ 这么大怎么选择 $x,y$ 呢?

考虑快速幂一样的把答案滚出来。详情见我的代码。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/544
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「CF623E」 Transforming Sequence
题目链接 没想到非 Chinese Round 也会出这么毒瘤的题目...... 题目大意:对于正整数序列 $A$,定义序列 $B$: $B_1=A_1,B_i=B_{i-1}\ or\ A_i,i\in[2,n]B $ 其中 or 为位或运算。 每一…
扫描二维码继续阅读
2019-03-14
标签
近期评论