【学习笔记】CF1864H Asterism Stream

发布时间:2024年01月04日

从一道 简单题 联想了过来。

Part 1

先复述一遍官方题解的做法:记几何级数 f ( x ) = a k b x f(x)=ak^{bx} f(x)=akbx(也就是等比数列), [ 2 l , 2 r ] [2l,2r] [2l,2r]区间内的DP值可以表示为若干个几何级数的和。本题中 k = 1 2 k=\frac{1}{2} k=21?,简记上述几何级数为 { a , b } \{a,b\} {a,b}

有递推式:

f x = k ( f x + 1 + f 2 x ) + 1 f_{x}=k(f_{x+1}+f_{2x})+1 fx?=k(fx+1?+f2x?)+1

对于 x ∈ [ l , r ] x\in [l,r] x[l,r],不难归纳得到

f x = k r ? x + 1 f r + 1 + ∑ i = 0 r ? x f ( 2 x + 2 i ) k i + 1 + ∑ i = 0 r ? x k i f_x=k^{r-x+1}f_{r+1}+\sum_{i=0}^{r-x}f(2x+2i)k^{i+1}+\sum_{i=0}^{r-x}k^i fx?=kr?x+1fr+1?+i=0r?x?f(2x+2i)ki+1+i=0r?x?ki

显然,第一项可以表示为 { k r + 1 f r + 1 , ? 1 } \{k^{r+1}f_{r+1},-1\} {kr+1fr+1?,?1},最后一项可以表示为 { 1 1 ? k , 0 } + { ? k r + 1 1 ? k , ? 1 } \{\frac{1}{1-k},0\}+\{-\frac{k^{r+1}}{1-k},-1\} {1?k1?,0}+{?1?kkr+1?,?1}。需要注意的是,应该写成关于 x x x的函数,且 k k k为常量。

大力化式子:

∑ { a , b } ∑ i = 0 r ? x a k b ( 2 x + 2 i ) k i + 1 = a k ? k 2 b x ∑ i = 0 r ? x k i ( 2 b + 1 ) = a k ? k 2 b x ? 1 ? k ( r ? x + 1 ) ( 2 b + 1 ) 1 ? k 2 b + 1 = a k ? k 2 b x ( 1 1 ? k 2 b + 1 ? k ( r + 1 ) ( 2 b + 1 ) 1 ? k 2 b + 1 k ? 2 b x ? x ) = a k 1 ? k 2 b + 1 k 2 b x ? k ( r + 1 ) ( 2 b + 1 ) 1 ? k 2 b + 1 k ? x = { a k 1 ? k 2 b + 1 , 2 b } + { ? k ( r + 1 ) ( 2 b + 1 ) 1 ? k 2 b + 1 , ? 1 } \begin{aligned} \sum_{\{a,b\}}\sum_{i=0}^{r-x}ak^{b(2x+2i)}k^{i+1}&=ak\cdot k^{2bx}\sum_{i=0}^{r-x}k^{i(2b+1)}\\&=ak\cdot k^{2bx}\cdot\frac{1-k^{(r-x+1)(2b+1)}}{1-k^{2b+1}}\\&=ak\cdot k^{2bx}\left(\frac{1}{1-k^{2b+1}}-\frac{k^{(r+1)(2b+1)}}{1-k^{2b+1}}k^{-2bx-x}\right)\\&=\frac{ak}{1-k^{2b+1}}k^{2bx}-\frac{k^{(r+1)(2b+1)}}{1-k^{2b+1}}k^{-x}\\&=\{\frac{ak}{1-k^{2b+1}},2b\}+\{-\frac{k^{(r+1)(2b+1)}}{1-k^{2b+1}},-1\} \end{aligned} {a,b}?i=0r?x?akb(2x+2i)ki+1?=ak?k2bxi=0r?x?ki(2b+1)=ak?k2bx?1?k2b+11?k(r?x+1)(2b+1)?=ak?k2bx(1?k2b+11??1?k2b+1k(r+1)(2b+1)?k?2bx?x)=1?k2b+1ak?k2bx?1?k2b+1k(r+1)(2b+1)?k?x={1?k2b+1ak?,2b}+{?1?k2b+1k(r+1)(2b+1)?,?1}?

其中 k 2 b x k^{2bx} k2bx k ? 2 b x k^{-2bx} k?2bx抵消这一步是可以预见的,因为求和上标的 x x x系数为负。

因此递推 log ? n \log n logn个区间即可,注意使用欧拉定理。

预处理出 1 ? 2 2 t ? 1 1-2^{2^{t}-1} 1?22t?1的逆元即可做到单次查询 O ( log ? 2 n ) O(\log^2 n) O(log2n)

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
const int mod=998244353;
int T;
ll n,inv2=(mod+1)/2;
ll fpow(ll x,ll y=mod-2){
    y=(y%(mod-1)+(mod-1))%(mod-1);
    ll z(1);
    for(;y;y>>=1){
        if(y&1)z=z*x%mod;
        x=x*x%mod;
    }return z;
}
vector<pair<ll,ll>>v,v2;
ll calc(ll x){
    ll y(0);ll tmp=x%(mod-1);
    for(auto e:v){
        ll a=e.fi,b=e.se;
        y=(y+a*fpow(inv2,b*tmp%(mod-1)))%mod;
    }return y;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n;
        ll l=n,r=2*n-1;v.clear();
        while(l>1){
            l=(l+1)/2,r=r/2;ll x=(fpow(inv2,r+1)*calc(r+1)%mod-fpow(inv2,r))%mod;
            v2.clear();
            for(auto e:v){
                ll a=e.fi,b=e.se,mul=fpow(inv2,2*b+1)-1;mul=fpow(mul);
                v2.pb({-a*inv2%mod*mul%mod,2*b%(mod-1)});
                ll tmp1=(2*b+1)%(mod-1),tmp2=(r+1)%(mod-1);
                x=(x+a*fpow(inv2,tmp1*tmp2%(mod-1)+1)%mod*mul%mod)%mod;
            }
            v=v2;v.pb({x,-1}),v.pb({2,0});
        }
        cout<<(calc(1)+mod)%mod<<"\n";
    }
}

Part 2

考虑简单题中的做法:首先得到转化后的递推式 f i = 2 f i ? 1 ? f i ? 1 2 [ i ? 2 ] + a f_{i}=2f_{i-1}-f_{\frac{i-1}{2}}[i\nmid 2]+a fi?=2fi?1??f2i?1??[i?2]+a(通常来说,我们希望递推涉及的项越少越好),而 i ? 1 2 \frac{i-1}{2} 2i?1?可以看作 ? i 2 ? \lfloor\frac{i}{2}\rfloor ?2i??,为什么我们只需要 log ? n \log n logn的空间?因为递推只涉及这 log ? n \log n logn个项,换句话说, f i , f ? i 2 ? , f ? i 4 ? , . . . f_i,f_{\lfloor\frac{i}{2}\rfloor},f_{\lfloor\frac{i}{4}\rfloor},... fi?,f?2i???,f?4i???,... 这些元素的信息是封闭的,当从 i ? 1 i-1 i?1递推到 i i i时我们可以根据 i i i包含的 2 2 2的个数得到转移矩阵(这里用到了取整函数的基本性质)。

因此,设 f i f_i fi?表示数列包含 i i i的概率,有递推式

f i = k ( f i ? 1 + f i 2 [ 2 ∣ i ] ) f_{i} =k(f_{i-1}+f_{\frac{i}{2}}[2\mid i]) fi?=k(fi?1?+f2i??[2i])

注意到若 x ∈ [ 1 , 2 k ) x\in [1,2^{k}) x[1,2k),则 v 2 ( x ) = v 2 ( x + 2 k ) v_2(x)=v_2(x+2^k) v2?(x)=v2?(x+2k)(二进制下末尾 0 0 0的个数),因此可以递推求出 [ 1 , 2 k + 1 ) [1,2^{k+1}) [1,2k+1)的矩阵乘积。

然而由于是矩阵的递推,因此非常慢,只能做到预处理 O ( log ? 4 n ) O(\log^4 n) O(log4n),查询 O ( log ? 3 n ) O(\log^3 n) O(log3n)

Part 3

可以先还是转化成对数列包含 i i i的概率求和,然后转化成对恰好等于 n ? 1 n-1 n?1的方案求和。然后数位DP,这就是CF1290F Making Shapes

还可以多项式。这是因为 n ? 1 n-1 n?1的二进制拆分固定,因此从高位到低位调整,发现实际上就是在做若干次前缀和。因此可以猜测答案就是次数为二进制位数 L L L的多项式。不过如果方案带权值的话显然就不对了(如前所述,答案应该是关于 x x x的几何级数)。

Part 4

众所周知矩阵乘法实在是太慢了,因此我曾经试图用多项式插值来代替矩阵乘法。现在想来这个想法是比较可笑的,因为矩阵乘法是用来加速递推的,而如果递推出来是几何级数那么显然就不能用多项式来求。

不过多项式插值还有其他的应用。例如我出的某一道题。🤔

文章来源:https://blog.csdn.net/cqbzlydd/article/details/135374451
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。