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);
}

Advertisement

spot_img

How does a raccoon...

Raccoons are ubiquitous across both rural woodlands and bustling...

We Tested Viral Kitchen...

📢 As an Amazon Associate, I earn from qualifying...

Brad Pitt and Ines...

Hollywood royalty made a stylish statement in Los Angeles...

Why Viral Kitchen Gadgets...

📢 As an Amazon Associate, I earn from qualifying...

US and rivals spar...

According to a report by Al Jazeera, diplomatic tensions...

Why Viral Kitchen Gadgets...

📢 As an Amazon Associate, I earn from qualifying...

How does a raccoon act with rabies?

Raccoons are ubiquitous across both rural woodlands and bustling suburban neighborhoods. While these masked foragers are generally cautious and nocturnal, their close proximity to...

We Tested Viral Kitchen Gadgets Here Is What You Must Know

📢 As an Amazon Associate, I earn from qualifying purchases.There comes a point when you realise that tolerating a frustrating situation is costing you...

Brad Pitt and Ines De Ramon walk ‘The Further Mis-Adventures of Cliff Booth’ premiere red carpet hand in hand

Hollywood royalty made a stylish statement in Los Angeles as Oscar-winning actor Brad Pitt arrived hand in hand with his partner, jewelry designer Inés...

Why Viral Kitchen Gadgets Is Currently Breaking the Internet

📢 As an Amazon Associate, I earn from qualifying purchases.Most products in this category disappoint within weeks. Cheap materials, vague instructions, and results that...

US and rivals spar over next UN boss as race lurches towards deadline

According to a report by Al Jazeera, diplomatic tensions among global powers have intensified as the United Nations nears the deadline to select its...

Why Viral Kitchen Gadgets Is Currently Breaking the Internet

📢 As an Amazon Associate, I earn from qualifying purchases.If you had told me six months ago that a single purchase would change how...

Curt Cignetti has built what Lincoln Riley can’t at USC: a team that knows how to win

College football is often dictated by resources, prestige, and five-star recruiting classes. Yet, the stark contrast between Curt Cignetti’s Indiana Hoosiers and Lincoln Riley’s...

I Tried Viral Kitchen Gadgets For 30 Days Here Is the Honest Truth

📢 As an Amazon Associate, I earn from qualifying purchases.There comes a point when you realise that tolerating a frustrating situation is costing you...

Top House Budget Dem Boyle: I’d Support ‘Major Appropriation’ for FAA Overhaul

In response to growing scrutiny over the reliability and resilience of national aviation infrastructure, Representative Brendan Boyle (D-PA) has publicly signaled strong support for...