寒假集训专题四-C.beautiful number

beautiful numbers

题意

输入a，b，n，由a和b组成的长n的数字，求各位数之和仍为a和b组成的数字的个数

思路

对n进行判断，发现就是求成功a，b个数的组合数之和。

通过对a个数的枚举来判断符合条件的a的个数，然后把组合数加入最后的结果

这里用到一个技巧-----组合数的计算以及乘法逆元

知识点：逆元

这题可以直接用费马小定理或者扩欧求，但若遇到数据量大的，会超时，如牛客寒假集训第6场牛妹的数学难题

利用费马小定理：

可得逆元为

线性求逆元方法

1.使用公式递推
这个公式的来源：
因为11^(-1)≡1
可得 i * i^(-1)恒等1，即求 i^-1
令k=p/i p=k * i + j 得 两边mod p 有 ki+j≡0(mod p)
两边除以 j * i 得：k * j^(-1) + i^(-1) ≡ 0 (mod p)
有 i^-1 ≡ -(p / i) * (p mod i) ^ (-1) (mod p)
可以使用递推实现，或者递归+记忆化
最后-p/i转化为 (p-p/i) 因为是负的 在c++中mod是按负的来所以要转化为floor取模 即可以加上要取模
（转化为正数）的数再取模

	f[0]=f[1]=1;
    inv[0]=inv[1]=1;
	for(int i=2;i<=N-1;i++)
	{
		f[i]=i;
		f[i]=f[i-1]*f[i]%mod;
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	}

2.前缀积求总逆元，再往回推

	fv[N-1]=qpow(f[N-1],mod-2);
	for(int i=N-1;i>=1;i--)
	{
		fv[i-1]=fv[i]*i%mod;
	}

代码

#include
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
using ll = long long;
const ll N=1e6+1;
const ll mod = 1e9+7;
ll a, b;
ll f[N];
//快速幂
ll qpow(ll x, ll n)
{
	ll base=1;
	while(n)
	{
		if(n&1)
		{
			base=base*x%mod;
		}
		x=x*x % mod;
		n=n>>1;
	}
	return base;
}
//记忆化阶乘，注意0的阶乘为1
void jiecheng()
{
	f[0]=1;
	f[1]=1;
	rep(i,2,N-1)
	{
		f[i]=i;
		f[i]=f[i]*f[i-1] % mod;
	}
}
//组合数的写法
ll c(ll m,ll n)
{
	return f[n]*qpow(f[m],mod-2)%mod*qpow(f[n-m],mod-2)%mod;
}
bool check(ll x)
{
	ll t;
	while(x)
	{
		t=x % 10;
		if(t != a && t != b)
		{
			return false;	
		}
		x=x/10;	
	} 
	return true;
}

signed main()
{
	jiecheng();
	
	ll ans = 0;
	ll n;
	ll temp;
	cin>>a>>b>>n;
	rep(i,0,n)
	{
		temp=a*i+b*(n-i);
		if(check(temp))
		{
			ans =(ans+c(i,n))% mod;
		}
	}
	cout<