hdu3398.zip_visual c

/* * Recently, lxhgww received a task : to generate strings contain '0's and '1's only, in which '0' appears exactly m times, '1' appears exactly n times. Also, any pref * x string of it must satisfy the situation that the number of 1's can not be smaller than the number of 0's . But he can't calculate the number of satisfied strings. * Can you help him? * * T(T<=100) in the first line is the case number. * Each case contains two numbers n and m( 1 <= m <= n <= 1000000 ). * * Output the number of satisfied strings % 20100501. * */ #include <iostream> #include <cstdio> #include <cstring> #include <string> #include <cstdlib> #include <queue> using namespace std; #define N 7 #define ll __int64 const int c_m = 20100501; int m;//0times,100yuan int n;//1times,50yuan int prime[N]; bool is_prime[N]; int p_num; int C_arr1[N]; int C_arr2[N]; int C_arr3[N]; int a1_len; void get_prime() { int i,j; p_num = 0; for( i = 2 ; i < N ; i++ ) { if( !is_prime[i] ) prime[p_num++] = i; for( j = 0 ; j < p_num && i*prime[j] < N ; j++) { is_prime[ i*prime[j] ] = 1; if( i%prime[j] == 0 ) break; } } } void div(int a[] , int t_num) { int i; int temp; for( i = 0 ; i < p_num && prime[i] <= t_num ; i++ ) { temp = t_num; while( temp ) { a[i] += temp/prime[i]; temp = temp/prime[i]; } } } int arr_pow(int a[]) { int i; int len = a1_len; ll sum = 1; ll tmp_num , tmp_p; for( i = 0 ; i < a1_len ; i++ ) { tmp_num = a[i]; tmp_p = prime[i]; while( tmp_num ) { if( tmp_num & 1 ) sum = (sum * tmp_p) % c_m; tmp_p = (tmp_p*tmp_p) % c_m; tmp_num >>= 1; } } return sum; } int C_Comb(int t_b , int t_s) { int i; a1_len = 0; int temp; //拆分阶乘 div(C_arr1 , t_b); div(C_arr2 , t_s+1 ); div(C_arr3 , t_b-t_s); //拆分n+1-m temp = n+1-m; for( i = 0 ; i < p_num && prime[i] <= temp ; i++ ) while( temp % prime[i] == 0 ) { C_arr1[i]++; temp /= prime[i]; } //约数相减 for( i = 0 ; i < p_num && prime[i] <= t_b ; i++ ) C_arr1[a1_len++] -= C_arr2[i] + C_arr3[i]; //快速幂乘便数组 return arr_pow( C_arr1 ); } int main() { int i,j; int temp; int t; get_prime(); for( i = 0 ; i < p_num ; i++ ) cout << prime[i] << ' '; cout << endl; cin >> t; while( t-- ) { cin >> n >> m; memset( C_arr1 , 0 , sizeof(C_arr1) ); memset( C_arr2 , 0 , sizeof(C_arr2) ); memset( C_arr3 , 0 , sizeof(C_arr3) ); temp = C_Comb( n+m , n ); cout << temp << endl; } return 0; }