c++ - Find the number of ways the N balls could be placed in the M boxes -
you have n
different balls numbered 1 n
, , m
different boxes numbered 1 m
.
input:
first line of input contains number of test cases t
. after that, next t
lines contain value of n
, m
.
output:
for each test case, print answer. can large, should print modulo 10^9 + 7
.
i tried below code, gives error:
#include<iostream> #include<cmath> #include<math.h> using namespace std; int main() { unsigned short int t; unsigned long int n,m; cin>>t; (int = 0; < t; i++) { cin>>n>>m; long int res; res= pow(m,n); int c=0; c=pow(10,9); res=res%(c + 7); cout<<res<<endl; } return 0; }
you must facing integer overflow
problem, that's why must have been getting wrong answer.
do following steps fix problem.
- change
unsigned long
long long
orunsigned long long
. (why? think). - use logarithmic user-defined function calculate value of
res = pow(m,n)
along modulo consideration side-by-side. boost program.
see code snippet check changes made:
#include<iostream> #define mod 1000000007 int main() { unsigned short int t; unsigned long long n , m , result; unsigned long long power(unsigned long long, unsigned long long); /*prototype of power*/ std::cin>>t; (int = 0; < t; i++) { std::cin >> n >> m; result = power(m , n); std::cout << result << std::endl; } return 0; } unsigned long long power(unsigned long long m, unsigned long long n) { if(n == 0) { return 1; } unsigned long long result = power(m , n/2); result = (result * result) % mod; if(n%2 == 1) { result = (result * m) % mod; } return result; }
Comments
Post a Comment