时间戳

首页 > 技术文章 > CF794G Replace All

CF794G Replace All

zjjws 2021-03-04 15:38 原文

是之前 XJ 搬过的题，不过我那次听得云里雾里没去订。

先考虑没有问号的做法。

Part 1 全部相等时的计算

对于 \(A,B\) 可以自己上下对应的两个串，必定是所有替换都是合法的，只要满足长度限制的串全都是合法的，这个很好判断，并且答案就是两个独立方案的乘积。具体的，是 \((\sum_{i=1}^n\limits 2^i)^2\)。

那么对于剩下的情况，必然存在某两个字母替换成 \(01\) 串后有交的部分，每个相交都对应着某段前缀与后缀的匹配。

Part 2 证明 \(A\) 和 \(B\) 都可以表示成另一个串的重复出现若干次的形式。

并且，基于某一步贪心，必定可以将原状态消成一个状态，头尾都满足：两个串的其中一个是 \(A\)，另一个是 \(B\)。

那么这样，\(A,B\) 中必然有一个是另一个的前缀，并且是后缀。

然后呢？

冷静头脑.jpg

放弃思考.jpg

等等，既然可以这么消 \(\cdots\)

钦定 \(|A|\ge |B|\)，然后 \(A-B\) 这个新串，下一步会匹配 \(A\) 或者 \(B\)，但不管是哪一个 \(A-B\) 的前缀一定是 \(B\)，除非它的长度小于 \(B\)。

而小于的情况则表明：\(A-B\) 是 \(B\) 的一段前缀。

先不考虑最后的那一步不够的情况，对于前面的，如果一直往后匹配到一个 \(A\)，那么会出现：

BB____
  BB____

那么就可以把 \(A\) 表示成若干个 \(B\) 加上一段 \(B\) 的前缀的形式。

那么现在就只剩下了两个串 \(B\) 和 \(B\) 的某一段前缀。

而另一种情况，你会发现，也是符合这个情况的。

在这么不停地转换之后，你会发现：这个过程非常类似求 \(\gcd\)，一直到留下的两个串长度为倍数关系的时候，才会停止，并且此时所有串都可以表现成一种形式。

按照这个过程，我们可以将 \(A\) 串 和 \(B\) 串都拆开，拆分成若干段相同的东西。它们两个串都是这个东西的不断重复。

并且依据这个过程，我们发现两个串长度的关系就是在求 \(\gcd\) 的过程。

所以我们证明了标题，并且知道这个公共串 \(C\) 的长度就是 \(\gcd(|A|,|B|)\)。

Part 3 剩余部分的答案计算

那么 \(A\) 和 \(B\) 的顺序自然就无所谓了，我们需要在意的只有个数。

\(A\) 和 \(B\) 所拥有的重复的串 \(C\) 的个数必须满足：\(num_A \cdot S_A +num_B \cdot S_B\) 这个东西上下相同（\(num\) 表示这个字母的个数，\(S\) 表示每个这个字母转化成 \(C\) 的个数）。

又发现这样考虑的话影响答案的是上下相差的 \(A,B\) 个数。

定义 \(a=\) 上面的 \(A\) 的个数减去下面的 \(A\) 的个数，\(b\) 的定义等价,不过是下减上。

\(a,b\) 若异号则直接无解。

那么 \(a\cdot |A|=b\cdot |B|\)，并且 \(|C|=\gcd(|A|,|B|)\)

若 \(a,b\) 都为 \(0\)，那么我们可以将上下看做同构，那么答案为：

\[\sum_{i=1}^n\limits \sum_{j=1}^n\limits 2^{\gcd(i,j)} \]

\[\sum_{p=1}^n 2^p\cdot (\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{p}\rfloor} [\gcd(i,j)=1]) \]

\[\sum_{p=1}^n 2^p\cdot (\ \sum_{d=1}^{\lfloor\frac{n}{p}\rfloor}\mu (d)\cdot (\lfloor\frac{n}{pd}\rfloor)^2\ ) \]

这个东西非常好做，你可以整除分块，也就是我写的 \(\operatorname O(n)\) 的，暴力是 \(\operatorname O(n\log n)\)，差别不大。

然后考虑 \(a,b\) 不为 \(0\) 的情况（其中一个为 \(0\) 无解）。我们可以先将 \(a,b\) 变成 \(\frac{a}{\gcd(a,b)},\frac{b}{\gcd(a,b)}\)，这样的话限制是等价的。那么此时 \(a,b\) 就已经互质了。

考虑上面那个式子，我们可以得到：\(\frac{|B|}{\gcd(|A|,|B|)}=a,\frac{|A|}{\gcd(|A|,|B|)}=b\)。

设 \(Ed=\lfloor\frac{n}{\max(a,b)}\rfloor\) 那么答案的计算就是：

\[\sum_{i=1}^{Ed}2^i \]

接下去，我们考虑怎么去考虑有问号的情况。

对于每一组 \(a,b\)，根据上面的分析，它们的答案有三种情况，我们定义 \(f_{a,b}\) 表示这个东西：

  • \(ab>0\) 时，是一个二的幂次的前缀和，即为 \(\sum_{i=1}^{\lfloor\frac{n}{\max(a,b)\rfloor}}\limits 2^i\)。

  • \(a=b=0\) 时，定义为前面所讲的同构的那个式子，莫反处理出来的那个。

  • 然后，在第二种情况下，有一小部分比较特殊，它们上下完全相同，此时的方案计算又要用到第一个式子，就是 \((\sum_{i=1}^n\limits 2^i)^2\)。

\(a,b\) 的定义照旧，不过新增两个变量 \(x,y\) 分别表示上面和下面的问号数量。

那么答案就可以表示为：

\[\sum_{i=0}^x\sum_{j=0}^y f_{a+i-j,b+(y-j)-(x-i)}\cdot \binom{x}{i}\cdot \binom{y}{j} \]

惊奇地发现 \(f\) 这一项只和 \(i-j\) 有关。

\[\sum_{i-j}f_{a+(i-j),(b+y-x)+(i-j)}\cdot \sum_{j=?}^? \binom{x}{i}\cdot \binom{y}{j} \]

\[\sum_{k=-y}^xf_{a+k,(b+y-x)+k}\cdot \sum_{j=?}^? \binom{x}{k+j}\cdot \binom{y}{y-j} \]

大致是这样的感觉，后面部分可以容斥然后范雷蒙德卷积搞成两个组合数的差。

具体的 \(j\) 的范围，还取决于枚举的 \(i-j\) 的大小。

这里考虑到，由于 \(j\) 的范围不合法只会使得一些照理来说定义为 \(0\) 的组合数 \(\binom{x}{k+j}\) 出现，而我刚刚因为将其当做未定义，会使得答案无法计算。

实际应该是可以直接将 \(j\) 的枚举范围改为 \([0,y]\) 的，然后范德蒙德卷积卷起来，也就是：\(\binom{x+y}{k+y}\)。

那么就做完了。

Part 4 Code

#include <vector>
#include <string>
#include <stdio.h>
#include <iostream>
#define LL long long
using namespace std;
inline LL rin()
{
    LL s=0;
    bool bj=false;
    char c=getchar();
    for(;(c>'9'||c<'0')&&c!='-';c=getchar());
    if(c=='-')bj=true,c=getchar();
    for(;c>='0'&&c<='9';c=getchar())s=(s<<1)+(s<<3)+(c^'0');
    if(bj)return -s;
    return s;
}

const int N=6e5+3;
const int M=1e9+7;
inline int prpr(int x,int y){return 1LL*x*y%M;}
inline int ksm(int x,int y){int ans=1;for(;y;y>>=1){if(y&1)ans=prpr(ans,x);x=prpr(x,x);}return ans;}
int pw[N];
int sl[N];
int sr[N];
int mu[N];
bool pri[N];
vector<int>prime;
int Gura_do_not_know_my_exist;

int CS[N];
inline int cs(int n)
{
    if(CS[n])return CS[n];
    int ans=0;
    for(int l=1,r,nw;l<=n;l=r+1)r=n/(nw=n/l),ans=(ans+prpr(mu[r]-mu[l-1],prpr(nw,nw)))%M;
    return CS[n]=ans;
}
inline void init(int n)
{
    pw[0]=1;for(int i=1;i<N;i++)pw[i]=(pw[i-1]<<1)%M;
    pw[0]=0;for(int i=2;i<N;i++)pw[i]=(pw[i-1]+pw[i])%M;
    sl[0]=1;for(int i=1;i<N;i++)sl[i]=prpr(sl[i-1],i);sr[N-1]=ksm(sl[N-1],M-2);
    sr[0]=1;for(int i=N-2;i>=1;i--)sr[i]=prpr(sr[i+1],i+1);
    mu[1]=1;
    for(int i=2,now;i<N;i++)
    {
        if(!pri[i])prime.push_back(i),mu[i]=-1;
        for(vector<int>::iterator j=prime.begin();j!=prime.end();j++){if((now=(*j)*i)>=N)break;pri[now]=true;if(i%(*j)==0)break;mu[now]=-mu[i];}
        mu[i]+=mu[i-1];
    }
    for(int l=1,r,nw;l<=n;l=r+1)
    {
        r=n/(nw=n/l);
        Gura_do_not_know_my_exist+=prpr(pw[r]-pw[l-1],cs(nw));
        Gura_do_not_know_my_exist%=M;
    }
    return;
}
inline int C(int a,int b){return (a<b||b<0)?(0):(prpr(sl[a],prpr(sr[b],sr[a-b])));}
inline int Gcd(int a,int b){return (!b)?(a):(Gcd(b,a%b));}

int n;
int ans;
string S,T;
inline void work(int i,int a,int b,int x,int y)
{
    a+=i;b+=i;
    if(!a&&!b){ans=(ans+prpr(Gura_do_not_know_my_exist,C(x+y,i+y)))%M;return;}
    if((1LL*a*b)<=0)return;
    int c=Gcd(a,b);a/=c;b/=c;
    ans=(ans+prpr(pw[n/max(a,b)],C(x+y,i+y)))%M;
    return;
}
inline bool check(int s,int t)
{
    if(s!=t)return false;for(int i=0;i<s;i++)if(S[i]!=T[i]||S[i]=='?'||T[i]=='?')return false;
    printf("%d\n",prpr(pw[n],pw[n]));return true;
}
int main()
{
    int s,t,a,b,x,y;a=b=x=y=0;
    cin>>S>>T;s=S.length();t=T.length();n=rin();init(n);
    if(check(s,t))return 0;
    for(int i=0;i<s;i++){if(S[i]=='A')a++;if(S[i]=='B')b--;if(S[i]=='?')x++;}
    for(int i=0;i<t;i++){if(T[i]=='A')a--;if(T[i]=='B')b++;if(T[i]=='?')y++;}
    for(int i=-y;i<=x;i++)work(i,a,b+y-x,x,y);
    if(s==t)
    {
        int cut=1;
        for(int i=0;i<s;i++)
        {
            if(S[i]=='?'&&T[i]=='?'){cut=(cut<<1)%M;continue;}
            if(S[i]=='?'||T[i]=='?'||S[i]==T[i])continue;
            cut=0;break;
        }
        ans=(ans+prpr(prpr(pw[n],pw[n])-Gura_do_not_know_my_exist,cut))%M;
        ans=(ans+M)%M;
    }
    printf("%d\n",ans);
    return 0;
}

推荐阅读