We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
There is nothing but modular arithemtic fact . Nothing else . Use fermats theorem to solve this . The denominator say D We have to find out the value of D ^ -1 % m . So , we know D^p-1 %p =1 (mod p) So , D^p-2 % p =D ^ -1 (mod p) . So , we have to find the power of D wrt to p-2 mod by m(1e9+7) . Then multiply the upper value and do modulo by m .That's all
My solution
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongintll;constllmod=1e9+7;llfact[2001];voidfill_up(){fact[0]=1;for(lli=1;i<=2000;i++){fact[i]=(fact[i-1]*i)%mod;}}llpower(lla,llb){llans=1;while(b){if(b&1)// check whether b is oddans=(ans*a)%mod;a=(a*a)%mod;b=b>>1;// b=b/2}return(ans%mod);}// Complete the solve function below.llsolve(lln,llm){llup=(fact[m-1+n])%mod;lldown=(fact[m-1]*fact[n])%mod;//cout<<n<<" "<<m<<" "<<up<<" "<<down<<" "<<fact[m-1]<<" "<<fact[n]<<" "<<endl;llans=(up*power(down,mod-2))%mod;returnans;}intmain(){fill_up();intt;cin>>t;while(t--){llN,M;cin>>N>>M;cout<<solve(N,M)<<endl;}}
Sherlock and Permutations
You are viewing a single comment's thread. Return to all comments →
There is nothing but modular arithemtic fact . Nothing else . Use fermats theorem to solve this . The denominator say D We have to find out the value of D ^ -1 % m . So , we know D^p-1 %p =1 (mod p) So , D^p-2 % p =D ^ -1 (mod p) . So , we have to find the power of D wrt to p-2 mod by m(1e9+7) . Then multiply the upper value and do modulo by m .That's all
My solution
My github solutions
https://github.com/joy-mollick/Problem-Solving-Solutions-Math-Greedy-