Beautiful Numbers - c++编程基础

题意：给你三个数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  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
  
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;  
}