【题解】bistu备战天梯训练赛（一）

（题目来源于atcoder abc 156）
比赛链接：https://vjudge.net/contest/405899
密码：bistuacm

A

白给题。题目读懂了按要求输出就可以了。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b,cnt=0;
    cin>>a>>b;
    if(a<10)cnt+=100*(10-a);
    cout<<cnt+b<<endl;
}

B

判断 在 进制下的位数，最简单的方法是不断除以 ，看除几次到0即可。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b,cnt=0;
    cin>>a>>b;
    while(a){
        a/=b,cnt++;
    }
    cout<<cnt;
}

C

给一个数组求方差。由于数据范围很小，所以 模拟就可以了。

#include<bits/stdc++.h>
using namespace std;
int a[11111];
int main(){
    int cnt=0,ma=0,mi=1e9;
    int n,i,j;
    cin>>n;
    for(i=0;i<n;i++)cin>>a[i];
    for(i=0;i<=100;i++){
        cnt=0;
        for(j=0;j<n;j++){
            cnt+=(a[j]-i)*(a[j]-i);
        }
        mi=min(mi,cnt);
    }
    cout<<mi;
}

D

答案显然是 。

可以用快速幂 求出（不会快速幂的可以自己百度一下），本题的难点在于怎么求两个组合数。
观察到 和 的范围都是200000，因此可以用组合数的公式来求：

分母部分可以用逆元将分数转化为整数。
这里给萌新们讲讲逆元的知识（会的大佬可以跳过了）
所谓逆元，即在模 意义下的值。设该值为 ，即 ，也就是满足 的那个
怎么求这个数呢？其实很简单。由费马小定理知，当 是素数且 和 互素时，
那么
也就是说， 就是 在模 意义下的逆元了。
要求 ，相当于求 乘以 的逆元。逆元的知识很重要，可以把分数当成整数进行各种运算。
所以分母部分直接乘以每个数的逆元就等价于除以这个数了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int mod=1e9+7;
ll power(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
ll inv(ll x){
    return power(x,mod-2);
}
ll C(ll n,ll k){
    ll res=1;
    for(ll i=1;i<=k;i++){
        res=res*(n-i+1)%mod*inv(i)%mod;
    }
    return res%mod;
}
int main(){
    int cnt=0,ma=0,mi=1e9;
    ll n,a,b;
    cin>>n>>a>>b;
    cout<<(power(2,n)-1-C(n,a)-C(n,b)+mod*1LL*1000)%mod;
}

E

首先不妨设人数为“0”的房间个数为 方案数为 。
那么最终的答案显然是。因为操作 次一定能形成人数为“0”的房间个数不大于 的局面，且大于 的局面一定不能形成。

可以这样来求：首先 个“0”房间的分布一共有 种，剩下的则是至少数量为1的房间，根据整数划分的结论，将 拆分成个正整数，共有 种。
所以最终的答案是 。
本题由于一共要求 个组合数，因此不能用上题的组合数求法。
正确的方法是利用递推：
观察。利用这个递推即可根据 求出所有的 。
求出所有的 后，全部加起来就是最终的结果了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int mod=1e9+7;
ll power(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
ll inv(ll x){
    return power(x,mod-2);
}
ll C(ll n,ll k){
    ll res=1;
    for(ll i=1;i<=k;i++){
        res=res*(n-i+1)%mod*inv(i)%mod;
    }
    return res%mod;
}
ll dp[200020],sum[200020];
int main(){
    int cnt=0,ma=0,mi=1e9;
    ll n,k,i;
    cin>>n>>k;
    dp[0]=1;
    dp[1]=n*(n-1)%mod;
    k=min(k,n);
    for(i=2;i<=n;i++){
        dp[i]=dp[i-1]*(n-i+1)%mod*inv(i)%mod*(n-i)%mod*inv(i)%mod;
    }
    sum[0]=dp[0];
    for(i=1;i<=k;i++){
        sum[i]=(sum[i-1]+dp[i])%mod;
        //cout<<dp[i]<<" "<<sum[i]<<endl;
    }

    cout<<sum[k];
}

F

// TODO
暂时不会做，等以后会了再补