CF1097H Mateusz and an Infinite Sequence

· · 题解

洛谷传送门 CF传送门

Solution

先考虑 |B|=1 的情况

题目中说的很明白：因为 gen_1=0 ，所以对于 \forall i，M_{i} 是 M_{i+1} 的前缀。

再思考，因为这是个无限长的序列，我们不能直接表示出来整个序列或者它需要求的那一部分，所以选择记录对答案有用的部分。

那么我们设 f_{i,j} 表示 M_{\infty} 的前 d^i 位加上 j 的答案数，那么转移方程就是：

f_{i,j}=\sum_{k=1}^df_{i-1,(j+gen_k)\%m}

其中初始状态：f_{0,i}=[i\leq B_1] 。

这样对于 l,r，设 ans_i 表示前 i 位中 B 严格大于的子串，我们就可以在 O(\log_d r) 的时间内将 ans_r-ans_{l-1} 求出。

现在考虑 |B|>1 的情况

可以发现和上面唯一不同的地方就是 |B| ，所以我们可以继续用这种转移方式，仍然设 f_{i,j} 为前 d_i 位加上 j 的答案数。

但是因为 |B| 改变，转移的时候就不能是单纯的转移答案了。不然两个区间合并时的后缀+前缀所增加的答案就被忽略了♪(^∇^*)

那我们现在转移 f_{i,j} 时，需要将 f_{i-1,(j+gen_k)\%m} 的全部信息合并，所以思考怎么合并两个区间的信息？

其实很简单，就是暴力拿 B 去匹配两个区间，然后记录这两个区间的前缀和后缀匹配 B 的情况，合并时暴力枚举。

时间复杂度为 O(nmd\log_d r) ，发现稍微超了一点。

仔细看一下前缀和后缀的暴力枚举部分：

我们设 suf_i 表示区间中长度为 n-i 的后缀可以和 B 长度为 n-i 的后缀匹配， pre_i 表示区间中长度为 i 的前缀可以和 B 长度为 i 的前缀匹配，那么增加的答案数就是 suf_i\And pre_i 中 1 的数量。

这就启发我们拿 \operatorname{bitset} 去优化。

现在时间复杂度为 O(\dfrac {nmd\log_d r}w) (￣▽￣)"

Code

#include<bits/stdc++.h>
#define ll long long
#define BI bitset<N>

using namespace std;
const int N=3e4+10;
int n,m,d,tot,gen[30],b[N];
ll len[70],l,r;
BI full;

template<typename T>inline void read(T &x){
    x=0; bool f=0;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=1;ch=getchar();}
    while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
    if(f) x=-x;
}

struct node{
    ll ans,len;
    BI pre,suf;
    node operator + (const node &a){
        node b;
        b.ans=ans+a.ans;
        b.len=len+a.len;
        b.pre=pre; b.suf=a.suf;
        if(len<n-1) b.pre&=(a.pre>>len)|(full<<n-1-len);
        if(a.len<n-1) b.suf&=(suf<<a.len)|(full>>n-1-a.len);
        if(len+a.len>=n){
            BI res=suf&a.pre;
            if(len<n-1) res&=(full>>n-1-len);
            if(a.len<n-1) res&=(full<<n-1-a.len);
            b.ans+=res.count();
        }
        return b;
    }
    void operator += (const node &a){*this=!len?a:*this+a;}
}f[70][70];

ll query(ll x){
    node res;
    res.ans=res.len=0;
    int tmp=0;
    for(int i=tot;~i;--i)
        for(int j=1;j<=d;j++){
            if(x>=len[i]){
                x-=len[i];
                res+=f[i][(tmp+gen[j])%m];
            }
            else{
                tmp=(tmp+gen[j])%m;
                break;
            }
        }
    return res.ans;
}

int main(){
    read(d); read(m);
    for(int i=1;i<=d;i++) read(gen[i]);
    read(n);
    for(int i=1;i<=n;i++) read(b[i]);
    for(int i=1;i<n;i++) full[i]=1;
    len[tot]=1;
    for(int i=0;i<m;i++){
        f[0][i].len=1;
        if(n==1) f[0][i].ans= i<=b[1];
        else{
            for(int j=1;j<=n-1;j++){
                f[0][i].pre[j]= i<=b[j+1];
                f[0][i].suf[j]= i<=b[j];
            }
        }
    }
    read(l); read(r);
    for(;len[tot]<=r/d;){
        ++tot; len[tot]=len[tot-1]*d;
        for(int i=0;i<m;i++)
            for(int j=1;j<=d;j++)
                f[tot][i]+=f[tot-1][(i+gen[j])%m];
    }
    printf("%lld\n",query(r)-query(l+n-2));
    return 0;
}