Advertisement
a53

veterani

a53
Mar 26th, 2020
197
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.30 KB | None | 0 0
  1. /**
  2. * Worg
  3. */
  4. #include <vector>
  5. #include <fstream>
  6. #include <algorithm>
  7.  
  8. std::ifstream fin("veterani.in");
  9. std::ofstream fout("veterani.out");
  10.  
  11. const int MOD = 666013;
  12.  
  13. std::vector<int> fact;
  14.  
  15. void precalculate_factorials(int limit) {
  16. fact = std::vector<int>(limit, 0);
  17. fact[0] = 1;
  18.  
  19. for (int i = 1; i < limit; i++) {
  20. fact[i] = 1LL * fact[i - 1] * i % MOD;
  21. }
  22. }
  23.  
  24.  
  25. int raise_to_power(long long base, long long exp) {
  26. long long ans = 1, aux = base;
  27.  
  28. for (long long i = 1; i <= exp; i <<= 1) {
  29. if (i & exp) {
  30. ans = ans * aux % MOD;
  31. }
  32. aux = aux * aux % MOD;
  33. }
  34.  
  35. return ans;
  36. }
  37.  
  38.  
  39. int modular_inverse(int value) {
  40. return raise_to_power(value, MOD - 2);
  41. }
  42.  
  43.  
  44. int compute_comb(int n, int k) {
  45. int answer = 1LL * fact[n] * modular_inverse(fact[k]) * modular_inverse(fact[n - k]) % MOD;
  46. return answer;
  47. }
  48.  
  49. int main() {
  50. int m, n;
  51. fin >> m >> n;
  52.  
  53. precalculate_factorials(m + n + 1);
  54.  
  55. int answer = 0;
  56. for (int k = 0; k <= std::min(n, m); k++) {
  57. int product = 1LL * compute_comb(m + n - k, m) * compute_comb(m, k) % MOD;
  58. answer += product;
  59.  
  60. if (answer >= MOD) {
  61. answer -= MOD;
  62. }
  63. }
  64.  
  65. fout << answer << "\n";
  66. return 0;
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement