当前位置:编程学习 > C/C++ >>

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++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,