题解：P16375 [IATI 2026] Evilution

· · 题解

题意简述

给定一段初始 DNA。

四种字符各有一个替换串。 每天会同时替换当前 DNA 中的所有字符。

每次询问给定 k,l,r。 求第 k 天区间 [l,r] 内， 四种字符分别出现了多少次。

解题思路

区间计数可以由两个前缀计数相减得到。 因此，只需解决前 x 个字符的计数问题。

先考虑一个字符展开若干天后的整体信息。 令 F_{k,c} 表示字符 c 展开 k 天后的信息。 其中记录总长度与四种字符的数量。

第零天的展开只有字符本身。 若 S_c 是字符 c 的替换串，转移为：

F_{k,c}=\sum_{d\in S_c}F_{k-1,d}

查询位置不超过 10^{18}。 所以，超过查询范围的预处理值都可以截断。 代码取 4\times10^{18} 作为上界。

还需快速求一个替换串前若干个字符的贡献。 对初始串和四个替换串， 分别预处理四种字符的前缀出现次数。

假设当前处理字符串 S。 其中每个字符还要继续展开 d 天。 那么 S 的前 p 个字符对应若干完整块。 这些块的总信息可由字符前缀和与 F 求出。

各块长度均为正数。 因此，完整块的总长度随 p 严格递增。 二分即可找到能完整取走的最长前缀。

取走这些完整块后，只有两种情况：

设下一个字符为 c。 第二种情况下，状态变为处理 S_c， 且剩余展开天数减一。

代码用循环执行这个过程。 每次循环都会减少展开天数。 这样无需递归，也只会追踪唯一的不完整块。

下面证明该过程得到正确的前缀计数。

一次替换后，当前字符串会变成若干展开块的拼接。 二分找到的最长前缀恰好包含所有完整块。 算法一次性加入这些块的完整信息。 若仍有剩余，只进入紧随其后的唯一一个块。

所以，每个被计入的位置恰好处理一次。 未进入目标前缀的位置不会被处理。 循环结束时，所得信息就是目标前缀的信息。

最后处理很大的 k。 每个替换串的长度至少为 2，因此：

|F_{60,c}|\ge 2^{60}>10^{18}+1

当 k>60 时，任何询问前缀都在首块内部。 向下穿过一层时， 只需进入对应替换串的首字符。

预处理首字符转移的倍增表。 先跳过 k-60 层， 即可转化为某个字符展开 60 天的前缀查询。

预处理需要 O(S) 的时间和空间。 其中 S 是五个字符串的长度上界。 每个前缀至多向下处理 60 层。 每层在一个字符串中二分， 故单次询问复杂度为 O(60\log S)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
__extension__ using i128=__int128;
const int N=100005;
const ll inf=4000000000000000000LL;
struct Data
{
    ll len,c[4];
};
string s[5];
int pre[5][4][N],go[61][4];
Data f[61][4];
int id(char c)
{
    if(c=='A')return 0;
    if(c=='C')return 1;
    if(c=='G')return 2;
    return 3;
}
ll cap(i128 x)
{
    return x>inf?inf:(ll)x;
}
void add(Data &x,const Data &y,int w)
{
    x.len=cap((i128)x.len+(i128)y.len*w);
    for(int i=0;i<4;i++)x.c[i]=cap((i128)x.c[i]+(i128)y.c[i]*w);
}
ll get_len(int z,int p,int k)
{
    i128 res=0;
    for(int i=0;i<4;i++)res+=(i128)pre[z][i][p]*f[k][i].len;
    return cap(res);
}
Data get(int z,int p,int k)
{
    Data res={};
    for(int i=0;i<4;i++)add(res,f[k][i],pre[z][i][p]);
    return res;
}
Data walk(int z,int k,ll x)
{
    Data res={};
    while(x)
    {
        int l=0,r=s[z].size();
        while(l<r)
        {
            int mid=(l+r+1)/2;
            if(get_len(z,mid,k)<=x)l=mid;
            else r=mid-1;
        }
        Data t=get(z,l,k);
        add(res,t,1);
        x-=t.len;
        if(!x)break;
        int c=id(s[z][l]);
        if(!k)
        {
            res.len++;
            res.c[c]++;
            break;
        }
        z=c+1;
        k--;
    }
    return res;
}
int jump(int c,ll k)
{
    for(int i=0;k;i++,k>>=1)if(k&1)c=go[i][c];
    return c;
}
Data prefix(ll k,ll x)
{
    if(!x)return {};
    if(k<=60)return walk(0,k,x);
    int c=jump(id(s[0][0]),k-60);
    return walk(c+1,59,x);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for(int i=0;i<5;i++)cin>>s[i];
    for(int i=0;i<5;i++)
    {
        int n=s[i].size();
        for(int j=1;j<=n;j++)
        {
            for(int k=0;k<4;k++)pre[i][k][j]=pre[i][k][j-1];
            pre[i][id(s[i][j-1])][j]++;
        }
    }
    for(int i=0;i<4;i++)
    {
        f[0][i].len=1;
        f[0][i].c[i]=1;
        go[0][i]=id(s[i+1][0]);
    }
    for(int k=1;k<=60;k++)
    {
        for(int i=0;i<4;i++)
        {
            int n=s[i+1].size();
            for(int j=0;j<4;j++)add(f[k][i],f[k-1][j],pre[i+1][j][n]);
            go[k][i]=go[k-1][go[k-1][i]];
        }
    }
    int q;
    cin>>q;
    while(q--)
    {
        ll k,l,r;
        cin>>k>>l>>r;
        Data x=prefix(k,r+1),y=prefix(k,l);
        cout<<x.c[0]-y.c[0]<<' '<<x.c[1]-y.c[1]<<' '<<x.c[2]-y.c[2]<<' '<<x.c[3]-y.c[3]<<'\n';
    }
    return 0;
}