题解：CF300C Beautiful Numbers

· · 题解

Beautiful Numbers 题解

首先，我们观察题面，可以发现每个极好的数都必须是好数。 那好数的 n 位加起来是好数那就是极好的数。

我们可以枚举 a 出现了 suma 次，则 b 出现了 n - suma 次也就是 sumb，如果 a \times suma + b \times sumb 是好数，那这个数就是极好的数。

那我们可以求解出长度为 n 且 a 出现 suma 次 b 出现 sumb 次的数有多少个。也就是 C(n,suma) 或 C(n,sumb)。

最后奉上代码：

#include <iostream>
using namespace std;
long long const P = 1000000007;
int  n, a, b;
long long ans=0, fact[1000005], inv[1000005], finv[1000005];

int C(int n, int m)//组合数的计算 
{
    if(n < m) 
        return 0;
    if(m == 0)
        return 1;
    return fact[n] * finv[m] % P * finv[n - m] % P;
 } 
bool check(int x){//检查一下每一位加起来是不是好数 
    while (x){
        if (x % 10 != a && x % 10 != b) return false;
        x /= 10;
    }
    return true;
}
int main()
{
    scanf("%d%d%d",&a,&b,&n);
    fact[0] = 1;
    for (int i = 1; i <= n; i++)
        fact[i] = fact[i - 1] * i % P;//计算阶乘 
    finv[0] = finv[1] = inv[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        int k=P/i, r=P%i; 
        inv[i] = ((-1 * k * inv[r] % P) + P) % P;//逆元 
        finv[i] = finv[i - 1] * inv[i] % P;//逆元的阶乘 
    }
    for (int suma = 0;suma <= n;suma++){
        int sumb = n - suma;
        if (check(sumb * b + suma * a)){
            ans = (ans + C(n,suma) % P) % P;//多模几下没问题 
        }
    }
    cout<<ans;
    return 0;//华丽收场 
}