本文主要是介绍CF 181 div2 C. Beautiful Numbers，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：C - Beautiful Numbers
题意：输入a，b，n，求满足长度为n且只由a，b组成的数字各位之和也只由a，b组成的组合数。
n的大小是10^6，受之前某个题的影响，这样想的：假设a<b,最少情况是n*a，最大的情况是n*b,搜一遍判一下，然后对于可行的解用扩展欧几里得求出满足条件的a,b的个数，然后求组合数。。。这个思路也行吧，时间用得比较多，但毕竟是自己想的，赶脚还是很不错的，做题就是要大胆。
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
#define maxn 1000010
typedef long long LL;
const long long mod =1000000007;
long long fac[maxn];
long long a,b,n;
void init()
{fac[0]=1;for(int i=1;i<maxn;i++)fac[i]=(fac[i-1]*i)%mod;
}
long long exgcd(long long a,long long b,long long &x,long long &y)
{if(b==0){x=1;y=0;return a;}else{long long ans=exgcd(b,a%b,x,y);long long t=x;x=y;y=t-a/b*x;return ans;}
}
bool is_ok(long long x)
{long long tmp=x;while(tmp){if(tmp%10!=a && tmp%10!=b)return false;tmp/=10;}return true;}
long long Pow(long long a,long long b)
{long long ans=1;while(b){if(b&1){b--;ans=(ans*a)%mod;}else{b/=2;a=(a*a)%mod;}}return ans;
}long long C(LL n,LL m)
{if(n<m)return 0;LL ans=fac[n]*Pow(fac[m]*fac[n-m]%mod,mod-2)%mod;return ans%mod;
}
long long gcd(long long a,long long b)
{if(b==0)return a;return gcd(b,a%b);
}
long long solve(long long c)
{long long x,y;long long aa=a,bb=b,g=gcd(a,b);if(c%g!=0)return 0;c/=g;aa/=g;bb/=g;exgcd(aa,bb,x,y);x*=c;x%=bb;if(x<0)x+=bb;y=(c-aa*x)/bb;while(x<=n || y>=0){if(x+y==n){return C(n,x);}x+=bb;y=(c-aa*x)/bb;}return 0;
}
int main()
{init();cin>>a>>b>>n;if(a>b)swap(a,b);long long ans=0;for(int i=a*n;i<=b*n;i++)if(is_ok(i)){if(i%gcd(a,b)==0){ans+=solve(i);ans%=mod;}}cout<<ans<<endl;return 0;
}
看了别人的代码，发现我想复杂了，别人是对n位进行分配，组成后的数字的各位之和是不是还是由那两个数字组成的，这样暴力的过程，就遍历组合（0，n）（1，n-1）到（n,0）吧，确实比我简单，= = 貌似我是进行了一个逆过程，还装逼用了扩展欧几里得，呵呵。。。
还好弄出来了，不然对不起这个900+人过的 combinatorics 了。（这题应该没有人跟我一样傻逼的用上面的方法做了吧。。。）
估计大部分人都是用下面这种方法过的吧：
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
#define maxn 1000010
typedef long long LL;
const long long mod =1000000007;
long long fac[maxn];
long long a,b,n;
void init()
{fac[0]=1;for(int i=1;i<maxn;i++)fac[i]=(fac[i-1]*i)%mod;
}
bool is_ok(long long x)
{long long tmp=x;while(tmp){if(tmp%10!=a && tmp%10!=b)return false;tmp/=10;}return true;}
long long Pow(long long a,long long b)
{long long ans=1;while(b){if(b&1){b--;ans=(ans*a)%mod;}else{b/=2;a=(a*a)%mod;}}return ans;
}long long C(LL n,LL m)
{if(n<m)return 0;LL ans=fac[n]*Pow(fac[m]*fac[n-m]%mod,mod-2)%mod;return ans;
}
int main()
{init();cin>>a>>b>>n;long long ans=0;for(int i=0;i<=n;i++)if(is_ok(a*i+b*(n-i))){ans=(ans+C(n,i))%mod;}cout<<ans<<endl;return 0;
}
这篇关于CF 181 div2 C. Beautiful Numbers的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
