【题解】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

判断 $n$ 在 $k$ 进制下的位数，最简单的方法是不断除以 $k$ ，看除几次到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

给一个数组求方差。由于数据范围很小，所以 $O(n*100)$ 模拟就可以了。

#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

答案显然是 $2^n-C^a_n-C^b_n-1$ 。

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

$C^a_n=\frac{n*(n-1)*...*(n-a+1)}{1*2*...*a}$

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

#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”的房间个数为 $k$ 方案数为 $g(n,k)$ 。
那么最终的答案显然是 $g(n,1)+g(n,2)+...+g(n,k)$ 。因为操作 $k$ 次一定能形成人数为“0”的房间个数不大于 $k$ 的局面，且大于 $k$ 的局面一定不能形成。

$g(n,k)$ 可以这样来求：首先 $k$ 个“0”房间的分布一共有 $C_n^k$ 种，剩下的则是至少数量为1的房间，根据整数划分的结论，将 $n$ 拆分成 $n-k$ 个正整数，共有 $C_{n-1}^{n-k-1}=C_{n-1}^k$ 种。
所以最终的答案是 $g(n,k)=C_n^k*C_{n-1}^k$ 。
本题由于一共要求 $k$ 个组合数，因此不能用上题的组合数求法。
正确的方法是利用递推：
观察 $C^i_n=C^{i+1}_n*(\frac{n-i}{i+1})$ 。利用这个递推即可根据 $C^0_n=1$ 求出所有的 $C^k_n$ 。
求出所有的 $g(n,i)$ 后，全部加起来就是最终的结果了。

#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
暂时不会做，等以后会了再补