Beautiful Numbers
题意:给你三个数a,b,n;求满足由a,b组成的n位的个数,且每个位置上的数之和也是用a,b组成;解析:由题意设a的个数为x,b的个数为y,那么x+y==n;因此枚举满足条件的x的值,然后对这x个a和y进行排列组合。
满足条件的个数为n!/(x!*y!);直接求解会超时。
因此,对该等式进行求逆元,A×inv( b ) % Mod;inv( b ) = pow( b , Mod - 2 );
带入求解。
// File Name: c.cpp // Author: bo_jwolf // Created Time: 2013年10月08日 星期二 15:11:26 #include<vector> #include<list> #include<map> #include<set> #include<deque> #include<stack> #include<bitset> #include<algorithm> #include<functional> #include<numeric> #include<utility> #include<sstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<ctime> using namespace std; const int maxn = 1000005; long long num[ maxn ]; #define Mod 1000000007 bool judge( long long n, int x, int y ){ while( n ){ int temp = n % 10; if( temp != x && temp != y ) return 0; n /= 10; } return 1; } long long Pow_mod( long long a, long long b ){ long long ans = 1; while( b ){ if( b & 1 ){ ans = ( ans * a ) % Mod; b--; } a = ( a * a ) % Mod; b >>= 1; } return ans; } int main(){ num[ 0 ] = 1; for( int i = 1; i < maxn; ++i ) num[ i ] = ( num[ i - 1 ] * i ) % Mod; int a, b, n; long long ans; while( scanf( "%d%d%d", &a, &b, &n ) != EOF ){ ans = 0; for( int i = 0; i <= n; ++i ){ int j = n - i; if( judge( ( i * a + j * b ), a, b ) ){ ans += ( num[ n ] * Pow_mod( num[ i ], Mod - 2 ) )% Mod * ( Pow_mod( num[ n - i ], Mod - 2 ) ) % Mod ; ans %= Mod; } } printf( "%lld\n", ans ); } return 0; }
补充:软件开发 , C++ ,