一个比较垃圾的做法,卡着时限过了这道题。
首先大胆猜个结论:要么 \(|s|=|t|\),此时 \(A,B\) 任取,要么存在字符串 \(c\) 和整数 \(x,y\) 使得 \(A=c^x,B=c^y\),其中 \(c^x\) 表示 \(x\) 个 \(c\) 拼接得到的结果。证明的话感觉还挺复杂的,可能要 border 引理之类的东西,不过我是先写了个暴力发现是 T 了而不是 WA 了才知道自己结论是正确的(
对 \(|s|\) 是否等于 \(|t|\) 分情况讨论:
-
如果 \(|s|\ne |t|\),先考虑暴力做法:枚举两个字符串中
A
的出现次数,再枚举 \(A,B\) 的长度 \(la,lb\),如果这种情况下 \(s,t\) 总长度相等,那么合法的充要条件是 \(s,t\) 都存在长度为 \(\gcd(la,lb)\) 的周期。考虑优化,假设两串中A
的出现次数分别为 \(c_1,c_2\),那么两字符串总长相等当且仅当 \(c1·la+(ls-c1)·lb=c2·la+(lt-c2)·lb\)。移项发现 \((c1-c2)(la-lb)=(lt-ls)·lb\)。考虑 \(d=\gcd(la,lb)\),那么你发现一个性质是 \(|\dfrac{la-lb}{d}|\) 必须要是 \(|lt-ls|\) 的因数,这样你考虑枚举 \(d\),枚举 \(\dfrac{lb}{d}\),枚举 \(\dfrac{la-lb}{d}\),然后预处理 \(way_{dif}\) 表示有多少种方法将问号换成A
或B
使得 \(c1-c2=dif\)(可以通过组合数求出),然后就可以通过判断是否有 \(\gcd(\dfrac{lb}{d},|\dfrac{la-lb}{d}|)=1\) 来做到快速更新答案。算下枚举量:\(d,\dfrac{lb}{d}\) 的总枚举量是 \(O(n\ln n)\) 的,\(\dfrac{la-lb}{d}\) 的枚举量是 \(d(n)\) 的,所以这部分复杂度 \(O(n\ln n·d(n))\)。 -
如果 \(|s|=|t|\),那么将贡献分为三部分计算:
- \(A=B\),方案数 \((\sum\limits_{i=1}^n2^i)·2^{\text{问号个数}}\)
- \(A\ne B\) 且 \(s\ne t\),那么枚举 \(\gcd(|A|,|B|)=d\),此时必须有 \(s,t\) 中
A
的个数相同,而选择 \(|A|,|B|\) 长度的方案数为 \(\sum\limits_{i=1}^{n/d}\sum\limits_{j=1}^{n/d}[i\perp j][i\ne j]\)。这是经典问题,预处理 \(\varphi(n)\) 的前缀和即可 \(O(1)\) 计算。 - \(A\ne B\) 且 \(s=t\),\(s=t\) 的方案数可以 \(O(n)\) 算出,设为 \(prd\),那么这部分贡献就是 \(prd·(2^{n+1}-2)·(2^{n+1}-2)-\text{前面被重复计算的贡献}\)。
这部分时间复杂度 \(O(n)\)。
const int MAXN=3e5;
const int MOD=1e9+7;
int qpow(int x,int e){int ret=1;for(;e;e>>=1,x=1ll*x*x%MOD)if(e&1)ret=1ll*ret*x%MOD;return ret;}
int fac[MAXN*2+5],ifac[MAXN*2+5];
void init_fac(int n){
for(int i=(fac[0]=ifac[0]=ifac[1]=1)+1;i<=n;i++)ifac[i]=1ll*ifac[MOD%i]*(MOD-MOD/i)%MOD;
for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%MOD,ifac[i]=1ll*ifac[i-1]*ifac[i]%MOD;
}
int pr[MAXN+5],prcnt,vis[MAXN+5],phi[MAXN+5],sphi[MAXN+5];
void sieve(int n){
phi[1]=1;
for(int i=2;i<=n;i++){
if(!vis[i])phi[i]=i-1,pr[++prcnt]=i;
for(int j=1;j<=prcnt&&pr[j]*i<=n;j++){
vis[pr[j]*i]=1;
if(i%pr[j]==0){phi[i*pr[j]]=phi[i]*pr[j];break;}
else phi[i*pr[j]]=phi[i]*phi[pr[j]];
}
}
for(int i=1;i<=n;i++)sphi[i]=(sphi[i-1]+phi[i])%MOD;
}
int binom(int n,int k){if(n<0||k<0||n<k)return 0;return 1ll*fac[n]*ifac[k]%MOD*ifac[n-k]%MOD;}
char s[MAXN+5],t[MAXN+5];int n,ls,lt,a1,a2,c1,c2,way[MAXN*2+5],pw[MAXN+5],res;
int main(){
init_fac(MAXN*2);sieve(MAXN);
scanf("%s%s%d",s+1,t+1,&n);ls=strlen(s+1);lt=strlen(t+1);
for(int i=1;i<=ls;i++){if(s[i]=='A')++a1;if(s[i]=='?')++c1;}
for(int i=1;i<=lt;i++){if(t[i]=='A')++a2;if(t[i]=='?')++c2;}
for(int i=(pw[0]=1);i<=n;i++)pw[i]=pw[i-1]*2%MOD;
for(int i=-lt;i<=ls;i++)way[i+lt]=binom(c1+c2,i+c2-(a1-a2));
if(ls==lt){
int sum=0;for(int i=-lt;i<=ls;i++)if(i!=0)sum=(sum+way[i+lt])%MOD;
for(int i=1;i<=n;i++)res=(res+1ll*pw[i]*sum)%MOD;
for(int i=1;i<=n;i++)res=(res+1ll*way[lt]*pw[i]%MOD*(2*sphi[n/i]-1))%MOD;
int prd=1;
for(int i=1;i<=ls;i++){
if(s[i]=='?'&&t[i]=='?')prd=2*prd%MOD;
else if(s[i]!='?'&&t[i]!='?'&&s[i]!=t[i])prd=0;
}
if(prd){
res=(res+1ll*prd*(2*qpow(2,n)-2)%MOD*(2*qpow(2,n)-2))%MOD;
for(int i=1;i<=n;i++)res=(res-1ll*prd*pw[i]%MOD*(2*sphi[n/i]-1)%MOD+MOD)%MOD;
}
}else{
vector<int>vec;
for(int i=1;i<=n;i++)if(abs(lt-ls)%i==0)vec.pb(i),vec.pb(-i);
static bool ok[505][MAXN+5];
for(int i=0;i<vec.size();i+=2)for(int B=1;B<=n;B++)
ok[i][B]=ok[i+1][B]=(__gcd(vec[i],B)==1);
for(int d=1;d<=n;d++){
int lim=n/d;
for(int i=0;i<vec.size();i++){
int x=vec[i];
for(int B=max(1-x,1);B<=min(lim,lim-x);B++){
if(ok[i][B]){
ll dif=1ll*B*(lt-ls)/x;
if(-lt<=dif&&dif<=ls)res=(res+1ll*pw[d]*way[dif+lt])%MOD;
}
}
}
}
}
printf("%d\n",res);
return 0;
}
标签:794G,lb,la,int,dfrac,Codeforces,Replace,ne,枚举
From: https://www.cnblogs.com/tzcwk/p/Codeforces-794G.html