# Codeforces#548 div2 solution

## 难度略微毒瘤的Div 2

Posted by yjjr's blog on April 5, 2019

# A. Even Substrings

## Code

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,ans=0;
int main(){
rep(i,1,n){
char ch=getchar();
if((ch-'0')%2==0)ans+=i;
}
cout<<ans<<endl;
return 0;
}


# B. Chocolates

## Code

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=2e5+6;
int a[maxn],tmp=2e9,n;
ll ans=0;
int main(){
dep(i,n,1)ans+=min(a[i],max(0,tmp-1)),tmp=min(tmp-1,a[i]);//,cout<<ans<<endl;
cout<<ans<<endl;
return 0;
}


# C. Edgy Trees

## Code

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=3e5+6;
const ll mod=1e9+7;
struct edge{int to,next,w;}e[maxn<<3];
int last[maxn],n,K,tmp=0,cnt=0,b[maxn];
bool vis[maxn];
ll ans;
void insert(int u,int v,int w){e[++cnt]=(edge){v,last[u],w};last[u]=cnt;}
inline ll qpow(ll x,ll y){
ll re=1;
x%=mod;
while(y){
if(y&1)re=(re*x)%mod;
y>>=1,x=(x*x)%mod;
}
return re;
}
void dfs(int x){
tmp++;
vis[x]=1;
reg(x)
if(!vis[e[i].to]&&!e[i].w)dfs(e[i].to);
}
int main(){
ans=qpow(n,K);
rep(i,1,n-1){
insert(u,v,w);insert(v,u,w);
}
rep(i,1,n)if(!vis[i]){dfs(i);b[++cnt]=tmp;tmp=0;}
rep(i,1,cnt)ans=((ans-qpow(b[i],K)+mod)%mod+mod)%mod;
cout<<ans<<endl;
return 0;
}


# D. Steps to One

## 分析

$f_i$表示写的序列最大公约数已经等于$i$的情况下写到结束为止的期望长度

$f_i=1+\frac 1 m \sum_{j=1}^n f_{gcd(i,j)}$

 反演之后变成$\sum_{d n} \mu(d) \lfloor \frac m d\rfloor$

## Code

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=2e5+6;
const ll mod=1e9+7;
int m,prime[maxn],cnt=0,mu[maxn],is_prime[maxn]={0};
void Pre(){
mu[1]=1;
rep(i,2,m){
if(!is_prime[i])prime[++cnt]=i,mu[i]=-1;
rep(j,1,cnt){
if(prime[j]*i>m)break;
is_prime[i*prime[j]]=1;
if(i%prime[j]==0){mu[i*prime[j]]=0;break;}else mu[i*prime[j]]=-mu[i];
}
}
}
inline ll qpow(ll x,ll y){
ll re=1;
while(y){
if(y&1)re=(re*x)%mod;
y>>=1,x=(x*x)%mod;
}
return re;
}
int main(){
Pre();
ll ans=1;
rep(i,2,m+1)if(mu[i])ans=(ans-mu[i]*(m/i)*qpow(m-m/i,mod-2)+mod)%mod;
cout<<ans<<endl;
return 0;
}


# E. Maximize Mex

## Code

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=1e4+6;
bool tmp[maxn];
struct edge{int to,next;}e[maxn<<1];
void insert(int u,int v){e[++cnt]=(edge){v,last[u]};last[u]=cnt;}
inline bool dfs(int x){
reg(x){
if(vis[e[i].to]==tot)continue;
vis[e[i].to]=tot;
return 1;
}
}
return 0;
}
inline int calc(int x){
//cout<<x<<"E\n";
rep(i,x,maxn-1){
tot++;
if(!dfs(i))return i;
}
}
}
int main(){