ABC156 Summary | xiaoh's Blog

ABC156 Summary(2020-2-22 20:00~21:40)

2020-2-23 xiaoh

A-Beginner

题意

给定 $Atcoder$ 的计分规则:给定两个正整数 $n,r$ ( $1\leq n\leq 100,0\leq r\leq 4111$ ),分别表示参赛轮数和 $Rating$ ,计分规则如:
1.当 $n<10$ 时, $r=表现分-100\times(10-n)$ ;
2.否则 $r=表现分$ .
现给定 $n和r$ ,求该场比赛的表现分.

题解

签到题,除了题面有点长没什么难度.

Code

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,r;
    cin>>r>>n;
    if(r<10) cout<<n+100*(10-r)<<endl;
    else cout<<n<<endl;
	return 0;
}

B-Digits

题意

给定两个正整数 $n和k$ ( $1\leq n\leq 10^9,1\leq k\leq 10$ ),求 $n$ 在 $k$ 进制下的位数.

题解

签到题,不解释

Code

#include<bits/stdc++.h>
using namespace std;
int n,k;
int ans=0;
int main()
{
    cin>>n>>k;
    while(n) n/=k,ans++;
    cout<<ans<<endl;
	return 0;
}

C-Rally

题意

在数轴上有 $n$ 个点( $1\leq n\leq 100$ ),第 $i$ 个点在 $x_i$ 的位置上.对于一个点 $i$ ,它到坐标为 $p$ 的点的代价为 $(x_i-p)^2$ ,现在你可以任意的选定一个点,求所有点到这个点距离的最小值.

题解

发现数据范围很小,因此 $O(n^2)$ 暴力搜索选定点的位置即可.

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=110,inf=999999999;
int n;
int a[MAXN];
int ans=inf;
int main()
{
    read(n);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<=100;i++)
    {
        int cnt=0;
        for(int j=1;j<=n;j++) cnt+=(a[j]-i)*(a[j]-i);
        ans=min(ans,cnt);
    }
    cout<<ans<<endl;
	return 0;
}

D-Bouquet

题意

有一个花瓶,里面可以插至少 $1$ 支的花.现在你有 $n$ 朵不同的花( $1\leq n\leq 10^9$ ),且花瓶中不能插入恰好 $a$ 朵或 $b$ 朵花( $1\leq a<b\leq min(n,2\times 10^5)$ ).求总的方案数对 $10^9+7$ 取模的结果

题解

先不考虑 $a和b$ 的限制,那么一共有 $2^n-1$ 种取法.恰好取 $a$ 朵花的方案数有 $C_n^a$ 中取法,对于 $b$ 同理.因此使用快速幂和逆元即可.

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const long long mod=1000000007;
long long n,a,b;
void ext_gcd(long long a,long long b,long long &x,long long &y)
{
    if(b==0)
    {
        x=1,y=0;
        return;
    }
    ext_gcd(b,a%b,y,x);
    y-=x*(a/b);
    return;
}
inline long long inverse(long long a)
{
    long long x,y;
    ext_gcd(a,mod,x,y);
    if(x<0) x+=mod;
    return x;
}
inline long long pow_mod(long long a,long long b)
{
    if(b==0) return 1;
    if(b==1) return a;
    long long x=pow_mod(a,b>>1);
    x*=x,x%=mod;
    if(b&1) x*=a,x%=mod;
    return x;
}
long long ans=0;
int main()
{
    read(n),read(a),read(b);
    ans=pow_mod(2,n);
    long long tmp=1;
    for(int i=1;i<=a;i++) tmp*=(long long)(n-i+1),tmp%=mod,tmp*=inverse(i),tmp%=mod;
    ans-=tmp;
    tmp=1;
    for(int i=1;i<=b;i++) tmp*=(long long)(n-i+1),tmp%=mod,tmp*=inverse(i),tmp%=mod;
    ans-=tmp;
    ans--;
    ans=(ans%mod+mod)%mod;
    write(ans),putchar('\n');
	return 0;
}

E-Roaming(No sumbitted)

题意

有一根长度为 $n$ 的数轴( $3\leq n\leq 2\times 10^5$ ),初始情况下从 $i$ 到 $n$ 的每个点上都有一个人.接下来有恰好 $k$ 次移动( $2\leq k\leq 10^9$ ),每次移动可以使一个人到其他的任意一个房间内.求最后每个房间内人数有多少种可能.

题解

不难发现恰好 $k$ 次移动后至多有 $min(n-1,k)$ 个房间内没有人.且对于满足上述条件的每一种人数情况,都有一种方法满足条件.所以问题就转化成了将 $n$ 分成至少 $n-k$ 个数的和,~~接下来生成函数+NTT就好啦~~考虑来排列组合.对于恰好有 $i$ 个房间没人的情况,总的方案数为 $C_{\,n}^{\,i}\times C_{\,n-1}^{\,n-i-1}$ ,即为从 $n$ 个点中选出 $i$ 个空点,其余用隔板法从和为 $n$ 的数中隔出 $n-i$ 个点作为其余每个房间的人数.接下来用逆元和组合数即可.

Code

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
const int MAXN=200010;
long long n,k;
long long c[MAXN];
long long c2[MAXN];
void ext_gcd(long long a,long long b,long long &x,long long &y)
{
	if(b==0)
	{
		x=1,y=0;
		return;
	}
	ext_gcd(b,a%b,y,x);
	y-=x*(a/b);
	return;
}
inline long long inverse(long long a)
{
	long long x,y;
	ext_gcd(a,mod,x,y);
	if(x<0) x+=mod;
	return x;
}
long long ans=0;
int main()
{
	cin>>n>>k;
	k=min(k,n-1);
	c[0]=c2[0]=1;
	for(int i=1;i<=n;i++)
	c[i]=c[i-1]*inverse((long long)i),c[i]%=mod,c[i]*=(n-i+1),c[i]%=mod;
	for(int i=1;i<=n;i++)
	c2[i]=c2[i-1]*inverse((long long)i),c2[i]%=mod,c2[i]*=(n-i),c2[i]%=mod;
	for(int i=0;i<=k;i++) ans+=c[i]*c2[n-i-1],ans%=mod;
	cout<<ans<<endl;
	return 0;
}

F-Modularness

题意

给定长度为 $k$ 的序列 $d$ ( $1\leq d\leq 5000,1\leq d_i\leq 10^9$ ),接下来有 $q$ 个询问( $1\leq q\leq 5000$ ),每个询问给定三个参数 $n,x,m$ ( $1\leq n,x,m\leq 10^9$ ),现构建一个 $a$ 序列,其递推公式如下:

a_i=\begin{cases} x & (i=0)\\ a_{i-1}+d_{(i-1)mod\, k} & (0<i<n) \end{cases}

求满足 $(a_i\, mod\, m)<(a_{i+1}\, mod \, m)$ ,其中 $0\leq i< n-1$ 的 $i$ 的数量.

题解

注意到数据范围不大,对于每一个询问都可以 $O(k)$ 的进行回答.考虑将 $d$ 序列的每一个数对 $m$ 取模后进行前缀和操作,那么不难发现所有的 $(a_i\, mod\, m)>(a_{i+1}\, mod \, m)$ 的数量即为 $\sum_{i=0}^{n-1}a_i /m$ .证明很简单,发现序列 $a$ 就是一个循环的前缀和,由于每个数都不小于 $0$ ,而取模后又一定小于 $m$ ,所以一旦和被取模一次,就一定会比前者小,所以只要统计被取模的次数,即除法去下整即可.接下来考虑 $(a_i\, mod\, m)=(a_{i+1}\, mod \, m)$ 的情况.显然,这种情况只有在存在一个 $p$ ,使 $d_p\,mod\,m=0$ 时才能够出现.我们只需统计每 $k$ 个中出现的次数,然后乘以出现的轮数,再加上最后不到一轮中的数量即可.因此对于每个询问使用前缀和按照上述操作随便算一下就好啦!

Code

#include<bits/stdc++.h>
#define int __int128
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x>=10) write(x/(__int128)10);
	putchar((int)(x%10)+'0');
	return;
}
const int MAXN=5010;
int k,q;
int a[MAXN];
int b[MAXN];
int s[MAXN];
signed main()
{
    read(k),read(q);
    for(int i=1;i<=k;i++) read(a[i]);
    for(int i=1;i<=q;i++)
    {
        int n,x,m;
        int cnt=0;
        read(n),read(x),read(m);
        for(int j=1;j<=k;j++)
        {
            b[j]=a[j]%m;
            if(b[j]==0) cnt++;
        }
        n--;
        for(int j=1;j<=k;j++) s[j]=s[j-1]+b[j];
        x%=m;
        x+=s[k]*(n/k);
        x+=s[n%k];
        cnt*=(n/k);
        for(int j=1;j<=n%k;j++)
        if(b[j]==0) cnt++;
        write(n-x/m-cnt),putchar('\n');
    }
	return 0;
}