#include<set>
#include<map>
#include<ctime>
#include<cmath>
#include<queue>
#include<bitset>
#include<string>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<sstream>
#include<numeric>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define For(i,x,y) for(int i=x,_y=y;i<=_y;++i)
#define Rep(i,x,y) for(int i=x,_y=y;i>=_y;–i)
#define pub push_back
#define pob pop_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
inline int read()
{
int x=0;char c=getchar();bool f=0;
for(;c>’9’||c<‘0′;f=c==’-‘,c=getchar());
for(;c>=’0’&&c<=’9’;x=(x<<1)+(x<<3)+c-‘0’,c=getchar());
return f?-x:x;
}
inline void write(int x)
{
if(x<0)putchar(‘-‘),x=-x;
if(x>=10)write(x/10);
putchar(x%10+48);
}
const int mo=1e9+7,N=1e6+5;
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
void renew(int &x,int y)
{
if((x+=y)>=mo)x-=mo;
}
int Pow(int a,int b)
{
int res=1;
for(;b;b>>=1,a=(ll)a*a%mo)if(b&1)res=(ll)res*a%mo;
return res;
}
int fac[2*N],inv[2*N],pw[2*N],p[2*N],g[2*N],phi[2*N];
bool vis[2*N];
void prepare(int n)
{
fac[0]=inv[0]=pw[0]=1;
For(i,1,n)fac[i]=(ll)fac[i-1]*i%mo;
inv[n]=Pow(fac[n],mo-2);
Rep(i,n-1,1)inv[i]=(ll)inv[i+1]*(i+1)%mo;
For(i,1,n)pw[i]=pw[i-1]*2%mo;
g[1]=phi[1]=1;vis[1]=1;
For(i,2,n)
{
if(!vis[i])p[++*p]=i,phi[i]=i-1;
for(int j=1;j<=*p&&(ll)i*p[j]<=n;++j)
{
vis[i*p[j]]=1;
if(i%p[j])phi[i*p[j]]=phi[i]*(p[j]-1);else
{
phi[i*p[j]]=phi[i]*p[j];
break;
}
}
}
For(i,2,n)g[i]=(g[i-1]+phi[i]*2)%mo;
}
int n,m,la,lb,ans;
char a[N],b[N];
int C(int n,int m)
{
return (ll)fac[n]*inv[m]%mo*inv[n-m]%mo;
}
int calc1(int c0,int c1)
{
if(c0<0)c0*=-1,c1*=-1;
int d=gcd(c0,c1);
c0/=d,c1/=d;
return (pw[n/max(c0,c1)+1]-2+mo)%mo;
}
int calc2(int c)
{
int mi=1,res=0;
For(i,1,la)
{
if(a[i]==’?’&&b[i]==’?’)mi=mi*2%mo;else
if(a[i]!=’?’&&b[i]!=’?’&&a[i]!=b[i]){mi=0;break;}
}
renew(c,mo-mi);
renew(res,(ll)(pw[n+1]-2+mo)*(pw[n+1]-2+mo)%mo*mi%mo);
For(i,1,n)renew(res,(ll)g[n/i]*c%mo*pw[i]%mo);
return res;
}
int a0,a1,a2,b0,b1,b2;
int main()
{
prepare(2000000);
scanf(“%s%s%d”,a+1,b+1,&n);
la=strlen(a+1);lb=strlen(b+1);
For(i,1,la)
{
if(a[i]==’A’)++a0;else
if(a[i]==’B’)++a1;else
if(a[i]==’?’)++a2;
}
For(i,1,lb)
{
if(b[i]==’A’)++b0;else
if(b[i]==’B’)++b1;else
if(b[i]==’?’)++b2;
}
int cnt=0;
For(i,-b2,a2)
{
int t1=a0-b0+i,t2=b1-a1+b2-a2+i,c=C(a2+b2,i+b2);
if(!t1&&!t2)
{
renew(ans,calc2(c));
assert(++cnt<2);
}else
if((ll)t1*t2>0)
{
renew(ans,(ll)c*calc1(t1,t2)%mo);
}
}
printf(“%d\n”,ans);
}
Tinkoff Challenge – Final Round (Codeforces Round #414, rated, Div. 1 + Div. 2), problem: (G) Replace All Solution In C/C++
#include<set>
#include<map>
#include<ctime>
#include<cmath>
#include<queue>
#include<bitset>
#include<string>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<sstream>
#include<numeric>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define For(i,x,y) for(int i=x,_y=y;i<=_y;++i)
#define Rep(i,x,y) for(int i=x,_y=y;i>=_y;–i)
#define pub push_back
#define pob pop_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
inline int read()
{
int x=0;char c=getchar();bool f=0;
for(;c>’9’||c<‘0′;f=c==’-‘,c=getchar());
for(;c>=’0’&&c<=’9’;x=(x<<1)+(x<<3)+c-‘0’,c=getchar());
return f?-x:x;
}
inline void write(int x)
{
if(x<0)putchar(‘-‘),x=-x;
if(x>=10)write(x/10);
putchar(x%10+48);
}
const int mo=1e9+7,N=1e6+5;
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
void renew(int &x,int y)
{
if((x+=y)>=mo)x-=mo;
}
int Pow(int a,int b)
{
int res=1;
for(;b;b>>=1,a=(ll)a*a%mo)if(b&1)res=(ll)res*a%mo;
return res;
}
int fac[2*N],inv[2*N],pw[2*N],p[2*N],g[2*N],phi[2*N];
bool vis[2*N];
void prepare(int n)
{
fac[0]=inv[0]=pw[0]=1;
For(i,1,n)fac[i]=(ll)fac[i-1]*i%mo;
inv[n]=Pow(fac[n],mo-2);
Rep(i,n-1,1)inv[i]=(ll)inv[i+1]*(i+1)%mo;
For(i,1,n)pw[i]=pw[i-1]*2%mo;
g[1]=phi[1]=1;vis[1]=1;
For(i,2,n)
{
if(!vis[i])p[++*p]=i,phi[i]=i-1;
for(int j=1;j<=*p&&(ll)i*p[j]<=n;++j)
{
vis[i*p[j]]=1;
if(i%p[j])phi[i*p[j]]=phi[i]*(p[j]-1);else
{
phi[i*p[j]]=phi[i]*p[j];
break;
}
}
}
For(i,2,n)g[i]=(g[i-1]+phi[i]*2)%mo;
}
int n,m,la,lb,ans;
char a[N],b[N];
int C(int n,int m)
{
return (ll)fac[n]*inv[m]%mo*inv[n-m]%mo;
}
int calc1(int c0,int c1)
{
if(c0<0)c0*=-1,c1*=-1;
int d=gcd(c0,c1);
c0/=d,c1/=d;
return (pw[n/max(c0,c1)+1]-2+mo)%mo;
}
int calc2(int c)
{
int mi=1,res=0;
For(i,1,la)
{
if(a[i]==’?’&&b[i]==’?’)mi=mi*2%mo;else
if(a[i]!=’?’&&b[i]!=’?’&&a[i]!=b[i]){mi=0;break;}
}
renew(c,mo-mi);
renew(res,(ll)(pw[n+1]-2+mo)*(pw[n+1]-2+mo)%mo*mi%mo);
For(i,1,n)renew(res,(ll)g[n/i]*c%mo*pw[i]%mo);
return res;
}
int a0,a1,a2,b0,b1,b2;
int main()
{
prepare(2000000);
scanf(“%s%s%d”,a+1,b+1,&n);
la=strlen(a+1);lb=strlen(b+1);
For(i,1,la)
{
if(a[i]==’A’)++a0;else
if(a[i]==’B’)++a1;else
if(a[i]==’?’)++a2;
}
For(i,1,lb)
{
if(b[i]==’A’)++b0;else
if(b[i]==’B’)++b1;else
if(b[i]==’?’)++b2;
}
int cnt=0;
For(i,-b2,a2)
{
int t1=a0-b0+i,t2=b1-a1+b2-a2+i,c=C(a2+b2,i+b2);
if(!t1&&!t2)
{
renew(ans,calc2(c));
assert(++cnt<2);
}else
if((ll)t1*t2>0)
{
renew(ans,(ll)c*calc1(t1,t2)%mo);
}
}
printf(“%d\n”,ans);
}
